Mathedu

Learn math by practice

Re-engineering Math

All news about Mathedu

Find Prime Numbers with Scilab®: Programing of the Sieve of Erastothenes

Find Prime Numbers with Scilab®: Programing of the Sieve of Erastothenes

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:

  1. write down the numbers from 2 to N (say 100)
  2. stripe the multiples of 2, except 2
  3. stripe the multiples of 3 not yet striped, except 3
  4. iterate the process for the next unstriped number k: stripe the multiples of k not yet striped, except k.
  5. 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.

-->P=PrimeNumbers(100000);
 
-->size(P)
 ans  =
 
    1.    9592.  
 
-->P(9500)
 ans  =
 
    98947.  

So, we have learned today that 98,947 was a prime number…

 

blog comments powered by Disqus
© 2016 Mathedu Postmaster