From charlesreid1

Prime number sieve

Advanced

See also: Project Euler/501

The Sieve of Eratosthenes requires O(N) space, so it can be problematic for finding very large prime numbers, larger than a trillion, beyond the working memory of a computer.

In this case we can utilize the segmented Sieve of Eratosthenes algorithm, which generates prime numbers between two numbers m and n.

The savings from implementing a segmented Sieve of Eratosthenes method come from the fact that the amount of space required is only as large as the square root of N, the end point, and that is a substantially smaller storage requirement.

This means M must be larger than the square root of N, however, otherwise we have overlap.

Implementing Segmented Sieve of Eratosthenes

Implementing a segmented sieve is not much different from implementing the regular method in small steps. Each time, we start with a list of prime numbers up to sqrt(N). Next, we need a special value called a Q value that indicates, for each prime, how far into our sequence (starting at the start index) we need to go to get to a number that that prime divides.

So for example, if we are performing the segmented Sieve of Eratosthenes on the interval 100 to 200, we start at 101 (considering odd numbers only), then 103, then 105 - and 105 is divisible by 3. So the Q value for the prime 3 is the number of steps we took to get to that multiple - or, 2.

Same thing for 5, since 105 is also a multiple of 5, we get a Q value of 2.

Likewise with 7, since 105 is also a multiple of 7, we get a Q value of 2.

For the next prime, 11, the number 121 is a multiple of 11, and 121 is (121-101)/2 = 10 elements down, so we get a Q value of 10.

And so on.

Now, each time we are looking at a segment, we start at that Q value, and we jump forward p units, and eliminate the number p units ahead as a potential factor. For 3, we started with a Q value of 2, so we start at 105. Now we jump ahead 3 units, to 111 (remember we are jumping in intervals of 2, since we are not considering the even numbers). 111 is also divisible by 3, and we can also eliminate it from our list of possible primes.

Now, we are only performing this operation over a relatively short interval - then we collect the results and move on. In the result above, going from 100 to 200, we might perform the above operations in intervals of 10 odd numbers each (covering 20 total numbers, which means we will take 5 steps to cover the whole range of 100 to 200). If we were doing a really big range, like 2 trillion to 3 trillion, we might take steps in intervals of a million.

References

Python implementation of segmented sieve of eratosthenes: http://ideone.com/iHYr1f

Programming Praxis description of algorithm: https://programmingpraxis.com/2010/02/05/segmented-sieve-of-eratosthenes/

More details and coverage: https://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes#10249801

Original reference: https://en.wikipedia.org/wiki/Generating_primes

Alternative: https://medium.com/@csnowleopard/project-euler-501-write-up-1fd39a097d03

Related

Flags