Sieve of Eratosthenes is an ancient algorithm in mathematics that allows us to find all prime numbers up to a specific integer value . It works well on small inputs (the maximum value of the interval is 10.000.000 – 20.000.000 ) .
I am not going to enter into too many details, as the algorithm itself is not very complicated and there are plenty resources on the web describing the concept of a sieve in general and the Eratosthenes Sieve in particular . Still I will implement this algorithm, for the sake of having a “complete” (far from the truth) reference on algorithms and data-structures .
The algorithm is based on the following technique:
|1. Create an array S of integers with size N (the maximum value of the interval). Mark all positions in the array as possible primes .|
|2. Start iterating the array from position 2 (the first prime number), and mark every multiple of 2 as non-prime: S[2*2], S[2*3], …|
|3. Find the next non-prime number (that wasn’t previously marked), in our case 3, and continue to mark as non-prime all its multiples: S[3*2], S[3*3], …|
|4. Find the next non-prime number (that wasn’t previously marked), in our case 5, and continue to mark as non-prime all its multiples: S[5*2], S[5*3], …|
|5. Repeat the logic, and stop when the next non-prime number, k, satisfies the following relationship k*k > p .|
Sieve of Eratosthenes pseudo-code:
FUNCTION SIEVE(max) sieve := ARRAY[2..max] FOR elem IN sieve elem := PRIME i := 2 WHILE i * i < max DO IF sieve[i] = PRIME THEN j := 2 WHILE j * i < max DO sieve[i * j] := NON-PRIME j := j + 1 i := i + 1 RETURN sieve