Sieve of Eratosthenes

required files are loaded...
prime numbers:
function sieve_eratosthenes(N)
    prime_numbers := empty list
    crossed_out := array with indices from 2 to N
    For all k from 2 to N
        crossed_out[k] := false
    current := 2
 
    While current ≤ N
        If crossed_out[current] is not set
            insert current into prime_numbers
            j := current + current
            While j ≤ N
                crossed_out[j] := true
                j := j + current
        current := current + 1
 
    While current ≤ N
        If crossed_out[current] is not set
            insert current into prime_numbers
        current := current + 1

The sieve of Eratosthenes is an algorithm that can be used to determine all prime numbers up to a given number. This number is referred to as N hereafter.

On this page you can visualize the sieve of Eratosthenes for numbers up to 1000.

If larger prime numbers are to be calculated, this can be done with the following calculator: list of prime numbers up to user-defined number
The calculator can calculate prime numbers up to 10,000,000, but does not display a visualization.

How it works

First, all the numbers from 2 to the predefined number N are written down. Then, starting from 2, go through the numbers in ascending order.

Whenever a number is not crossed out, it is a prime number. This is added to the list of prime numbers and all multiples of this prime number up to N are crossed out.

If the current number is crossed out, then it is not a prime number and nothing else is done with it.

If the current number is greater than N, then all numbers up to N that are not prime numbers have already been crossed out. Therefore, the remaining numbers that are not crossed out can be added to the list of prime numbers without having to cross out their multiples.

Example

As an example, all prime numbers up to 100 are to be determined.

First, all the numbers from 2 to 100 are written down and the list of prime numbers is still empty.
Sieve of Eratosthenes - Initialization
2 is not crossed out. Therefore, 2 is included in the list of prime numbers and the multiples of 2 are crossed out.
2 is a prime number. The multiples of 2 are crossed out.
3 is also not crossed out. Therefore, 3 is a prime number. 3 is added to the list of prime numbers and the multiples of 3 are crossed out.
3 is a prime number. The multiples of 3 are crossed out.
4 is crossed out. This means that 4 is not a prime number.
4 is not a prime number. Nothing else is done with the 4.
5 is a prime number. It is therefore included in the list of prime numbers and the multiples of 5 are crossed out.
5 is a prime number. The multiples of 5 are crossed out.
6 is crossed out. 6 is therefore not a prime number.
6 is not a prime number. Nothing else is done with the 6.
7 is not crossed out and is therefore a prime number. 7 is added to the list of prime numbers and the multiples of 7 are crossed out.
7 is a prime number. The multiples of 7 are crossed out.
8, 9 and 10 are crossed out and therefore not prime numbers.
8, 9 and 10 are not prime numbers - Sieve of Eratosthenes
11 is greater than 100 = 10. Therefore, all numbers that are not prime numbers and are less than or equal to 100 have already been crossed out. Thus, the numbers between 11 and 100 that are not crossed out are included in the list of prime numbers.
Sieve of Eratosthenes - All prime numbers up to 100

Reasons

Why is it not a prime number if the current number is crossed out?

If the current number is crossed out, then in one of the previous steps there was a number that is greater than 1 and less than the current number and that is a divisor of the current number. This means that the current number is not a prime number.

Why do the multiples of numbers that are crossed out not have to be crossed out?

If the current number is crossed out, then there is at least one smaller number that is greater than 1 and is a divisor of the current number. Since every multiple of a number is also a multiple of the divisor of this number, the multiples of the crossed-out current number have already been crossed out.

Why is it a prime number if the current number is not crossed out?

If the current number is not crossed out, then there is no number that is greater than 1 and less than the current number and that is a divisor of the current number. Otherwise, the current number would have already been crossed out in one of the previous steps. This means that the current number is a prime number.

Why have all numbers that are not prime numbers been crossed out if the current number is greater than N?

If you multiply 2 or more numbers that are all greater than N, you get a number that is greater than N. Therefore, the prime factorization of every number that is less than or equal to N contains at least one prime factor that is less than or equal to N. If the current number is greater than N, then all multiples of numbers that are less than or equal to N have already been crossed out. This means that there cannot be any numbers that are less than or equal to N that are not prime numbers but have not yet been crossed out.

Pseudocode

function sieve_eratosthenes(N)
    prime_numbers := empty list
    crossed_out := array with indices from 2 to N
    For all k from 2 to N
        crossed_out[k] := false
    current := 2
 
    While current ≤ N
        If crossed_out[current] is not set
            insert current into prime_numbers
            j := current + current
            While j ≤ N
                crossed_out[j] := true
                j := j + current
        current := current + 1
 
    While current ≤ N
        If crossed_out[current] is not set
            insert current into prime_numbers
        current := current + 1

Implementation

Sieve of Eratosthenes in Java:

Eratosthenes.java

TestClass.java

good explanatory videos on Youtube

Share:FacebookTwitter