Eratosthenes Magic Sieve

Surely everyone who reads this post is not just used, or at least heard about the sieve of Eratosthenes - the method of finding prime numbers. The very problem of obtaining prime numbers occupies a key place in mathematics; some cryptographic algorithms, such as RSA, are based on it. There are quite a few approaches to this problem, but in this article I will focus on some modifications of the simplest of them - the sieve of Eratosthenes.
The sieve principle is simple: let us need to find simple numbers in the interval from one to some N <= 10 ^ 6 . We get an array of N elements and fill it with true. Then we consistently go through it to the root of N, and meeting true, we delete all the numbers with this step up to N. The algorithm looks compact and simple, I quote it in java.

1. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
2. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
3. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
4. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
5. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;
6. Arrays.fill(isPrime, true ); isPrime[ 1 ] = false ; for ( int i= 2 ; i*i < N; i++) if (isPrime[i]) for ( int j=i*i; j < N; j+=i) isPrime[j] = false ;

The algorithm works for O (N * log (log (N))) , so it is quite suitable for small numbers. Consider the case when we need to find prime numbers not from one to N, but from n to m. Let us have limitations 1 <= m <= n <= 10 ^ 9; nm <= 10 ^ 6 . Here we need to apply an algorithm called a double sieve. It consists in finding primes from the root of n, then storing them in a separate array and “striking out” these primes in the same way with a certain step, but from the interval [m, n] we need. Briefly, this algorithm will look like this:

1. int primes = new int [P]; // fill it simple to the root of n
2. boolean sieve = new boolean [nm + 1 ]; // secondary sieve
3. Arrays.fill (sieve, true );
4. for ( int i = 0 ; i <P; i ++) {
5. int h = m% primes [i];
6. int j = h == 0 ? 0 : primes [i] - h;
7. for (; j <= nm; j + = primes [i])
8. sieve [j] = false ;

')
So you can cope with ranges sufficiently remote from zero. Now we come to the most interesting point: what if we need to output prime numbers from 0 to N = 10 ^ 8 ? If we recall the asymptotics, then at first glance it seems real even for a regular sieve, but looking at the memory costs: 10 ^ 8 * 4 = 400MB, we see that the problem is not so trivial, especially if we have tight time constraints. To solve this problem, we can distinguish two approaches, namely:

• sieve packaging
• cache memory

Consider them in more detail. Packing is this: in modern programming languages, the type of boolean takes on average from one to four bytes, although it can be encoded with just one bit. Therefore, we can create an array of integers and work with each of them as a bitwise mask, thereby saving memory 8-30 times. The advantages are immediately visible, but now let's dwell a little more on the second idea, which is guaranteed to speed up the sieve several times.
Many people know that in our computer there is a cache memory between the processor and RAM, it is much faster to work with it than from the RAM, but its size is limited. For example, when working with a large array, the processor loads a part of it into the cache, works with it, then transfers it back to the operational one, loads another, and so on. And now let us remember our sieve algorithm: we erased every prime number from the entire array, walking along it from beginning to end. Therefore, the processor will load the different segments of the array into the cache many times and the speed on this will be greatly lost. This approach proposes to minimize the cost of copying an array from one memory to another. This is easy to do if you divide our entire gap into pieces, up to 3 * 10 ^ 4 elements, which is approximately equal to the size of the cache and work with them in order. Then we will deal with the entire array for the minimum number of downloads. It will look something like this:

1. int CACHE = 30000 ; // cache size
2. int M = ( int ) Math .sqrt (N) + 1 ;
4. int primes = new int [P]; // array of primes to the root of N
5. boolean segment = new boolean [CACHE]; // secondary sieve
6. for ( int I = M- 1 ; I <N; I + = CACHE) {
7. Arrays.fill (segment, true );
8. for ( int i = 0 ; i <P; i ++) {
9. int h = I% primes [i];
10. int j = h> 0 ? primes [i] - h: 0 ;
11. for (; j <CACHE; j + = primes [i])
12. segment [j] = false ;
13. }
14. for ( int i = 0 ; i <CACHE; i ++) {
15. if (segment [i] && (i + I <N)) {
16. out .println (i + i); // print a prime number on the screen
17. }
18. }
19. }

Using this method, we greatly accelerate our sieve, practically without complicating it, for many tasks it helps a lot, for example, one of them: TDPRIMES , you can practice on this task and see well that a regular sieve doesn’t fit in 2.8.