Sieve of Eratosthenes

Prime number sieve

Advanced

See also: Project Euler/Problem 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.