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 10\\;000\\;000. For higher numbers, more efficient algorithms should be used (Lehmann test, Rabin-Miller test...).

Description

The algorithm consists of these steps:

  1. 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.
  2. Pick the first unmarked number n in the list and mark it as a prime.
  3. Mark all multiples of n as composite numbers.
  4. 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 m and n and it must hold, that m \\leq \\sqrt{upper\\;bound} or n \\leq \\sqrt{upper bound}. After the termination all unmarked numbers should be marked as primes.

Asymptotic complexity

The asymptotic complexity of the sieve of Eratosthenes is Ο(n \\cdot\\log(\\log n)), where n 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.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Cross out all multiples of 2 (mark 2 as a prime)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Cross out all multiples of 3 (mark 3 as a prime)
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

5 > sqrt(20), we are finished.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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 << " ";     
    }
}







       
 

Place for your banner

Here is the position ready for our customer's banners.