The sieve of Eratosthenes is a simple method for finding all prime numbers less or equal to some given upper bound. The algorithm was invented by an ancient Greece mathematician Eratosthenes of Cyrene approximately 200 BC. It is one of the most efficient methods for finding primes which are less then . For higher numbers, more efficient algorithms should be used (Lehmann test, Rabin-Miller test...).
Description
The algorithm consists of these steps:
- Write down all integers less or equal to the upper bound and higher than 2 (1 is not a prime) and set them as unmarked.
- Pick the first unmarked number n in the list and mark it as a prime.
- Mark all multiples of n as composite numbers.
- If the contains some unmarked number – GOTO: 2.
We can improve the termination condition (step 4) by checking that the first number in the list is higher than the square root of the upper bound – if the number is composite, than it must have at least two divisors and
and it must hold, that
or
. After the termination all unmarked numbers should be marked as primes.
Asymptotic complexity
The asymptotic complexity of the sieve of Eratosthenes is , where
is the upper bound.
Example
Find all prime numbers less than 20.
Solution
Write down all numbers less or equal to 20, starting at 2.
Cross out all multiples of 2 (mark 2 as a prime)
, we are finished.
Code
/**
* Sieve of Eratosthenes
* @param upperBound upperBound + 1 - first number, which wont be evaluated
*/
public static void sieveOfEratosthenes(int upperBound){
boolean[] sieve = new boolean[upperBound];
//true == is composite
//false == is prime
sieve[0] = sieve[1] = true; //0 and 1 are not primes
for(int i = 2; i <= Math.sqrt(sieve.length); i++){
if(sieve[i] == true) continue;
for(int j = 2*i; j < sieve.length; j += i){
sieve[j] = true; //the number is composite
}
}
printSieve(sieve);
}
/**
* Print out the sieve (primes)
* @param sieve sieve, true == number is composite, false == number is a prime
*/
private static void printSieve(boolean[] sieve) {
System.out.println("Primes less than " + sieve.length);
for (int i = 2; i < sieve.length; i++) {
if(sieve[i] == false) System.out.print(i + " ");
}
}
/**
* Sieve of Eratosthenes
* @param upperBound upperBound + 1 - first number, which wont be evaluated
*/
void sieveOfEratosthenes(int upperBound){
bool * sieve = new bool[upperBound];
for(int i = 0; i < upperBound; i ++){
sieve[i] = false;
}
//true == is composite
//false == is prime
sieve[0] = sieve[1] = true; //0 and 1 are not primes
for(int i = 2; i <= sqrt((double)upperBound); i++){
if(sieve[i] == true) continue;
for(int j = 2*i; j < upperBound; j += i){
sieve[j] = true; //the number is composite
}
}
printSieve(sieve, upperBound);
delete[] sieve;
}
/**
* Print out the sieve (primes)
* @param sieve sieve, true == number is composite, false == number is a prime
* @param size length of the sieve
*/
void printSieve(bool * sieve, int size) {
for (int i = 2; i < size; i++) {
if(sieve[i] == false) cout << i << " ";
}
}