homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightNumber theory

Prime numbers. Sieve of Eratosthenes

The calculator finds prime numbers using "Sieve of Eratosthenes" method.

This calculator find prime numbers using method, known from ancient times as the Sieve of Eratosthenes. Let us recall that prime numbers have no other divisors except themselves and 1.
As a result of the calculator's work, a matrix containing composite numbers (gray) and prime numbers (black) will be displayed.

PLANETCALC, Sieve of Eratosthenes

Sieve of Eratosthenes

Sieve
 



It was a demo calculator having a naive algorithm. The range of numbers is limited to 1000. The calculator and its source code would rather be useful for those who want to understand the logic of the ancient Greek scientist who invented the method in the 3rd century BC.
The following calculator evolves the Eratosthenes idea, it has a memory-optimised implementation and fewer excessive operations. Using this calculator (if your computer allows it), you can try to find prime numbers up to several billion. However, be careful - with a large boundary, the memory and processor of your device will be mercilessly used.

PLANETCALC, Sieve of Eratosthenes, optimised

Sieve of Eratosthenes, optimised

Prime numbers count
 
Execution time, ms
 
Output time, ms
 

All found prime numbers can be downloaded as a csv file, but here I warn you again - everything happens in the memory of your computer and when downloading, five times the amount of memory will be grabbed, compared to that necessary for storing numbers. My old laptop with 4GB of RAM coped quite easily with finding 26+ million primes from the half-billion range, but I could not download it as csv.

Sieve of Eratosthenes algorithm

The algorithm in a pseudocode:

//Boundary
n;
//fill an array with ones (upper bound = n)
a ⟵ [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1...];
//first loop
for i=2,3,4..≤n:
    if  a[i] = 1:
         //second loop
         for j = 2i,3i,4i .. ≤n:
              a[i]⟵0
output ⟵ all i in the range 2 ≤ i ≤ n, for which the condition a[i]=1 is met

Algorithm optimization

  • as it is easy to see the original algorithm is passed several times over the same array elements, to avoid this we change the following
    • first loop для i=2,3,4..while i2≤n
    • second loop: j=i2,i2+i,i2+2i... ≤n
  • instead boolean type of 1 byte we can use 1 bit - to 8 times reduce the memory required
  • as it is easy to see all even numbers except 2 are not prime, taking this fact into account, we do the following:
    • reduce the amount of memory required by another half
    • change the algorithm in this way:
      //first loop
      for i=3,5,7..while  i²≤n
      if  a[(i-1)/2] = 1:
       //second loop
       for j = i²,i²+2i,i²+4i .. ≤n:
            a[(i-1)/2]⟵0
      output ⟵ 2, all odd i in the range: 3 ≤ i ≤ n, for which the condition a[(i-1)/2]=1 is met
URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Prime numbers. Sieve of Eratosthenes

Comments