The Sieve of Erasthotenes is a very old algorithm to find by elimination the prime numbers up to a given integer N.
The manual process is so:
- write down the numbers from 2 to N (say 100)
- stripe the multiples of 2, except 2
- stripe the multiples of 3 not yet striped, except 3
- iterate the process for the next unstriped number k: stripe the multiples of k not yet striped, except k.
- continue until you get no more unstriped multiples before N
The unstriped remaining numbers are the numbers that are not a multiple of any previous number. Thus they have no divisor except themselves and 1, that is the definition of a prime number.
Until the recent times, the Sieve of Erasthothene could only be used for small prime numbers, say until 100.
But nowadays, we have processors with programing languages, so that we can apply the algorithm to much bigger numbers.
For the scientific programing language Scilab®, we may use the following script:
function P=PrimeNumbers(N) // computes the prime numbers up to the integer N // applies the Sieve of Erastotenes // Initialisation IsPrime(1)=%f; for k=2:N IsPrime(k)=%t; end // Sieve of Erastones for k=1:N // number not yet erased if IsPrime(k) // Erase the multiples of k // from 2*k to N by steps of k for n=2*k:k:N IsPrime(n)=%f; end end end // The prime numbers are at the indexes set to %t (true) P=find(IsPrime); endfunction
We may then calculate the prime numbers up to a very big number, for instance 100,000.
So, we have learned today that 98,947 was a prime number…