Sieve of Eratosthenes

The sieve of Eratosthenes is the classical method of generating prime numbers. The
procedure is very easy to implement in Mathematica. We make a list of integers
and remove the multiples of two, of three, and so on, until all we are left with are
primes. If we generate a table of primes up to n, then it is necessary to eliminate
the multiples of the primes up to square root of n.


  SieveOfEratosthenes[n_]:= 
           Module[ {t,P,i=1,x},
           t=N[Sqrt[n]];
           P=Range[2,n];
           While[ P[[i]] <= t,
             
            x=Table[k P[[i]],
                       {k,P[[i]], Floor[n/P[[i]]]}];
                        
            P=Complement[P,x];
             i++];
            Return[P]]


  SieveOfEratosthenes[100]

Remarks: Do not use this sieve to generate primes for n more than 10^5 as it is
likely to be very slow. For larger n, it is better to modify the sieve to generate
primes between n1 and n2, by reading in a list of primes up to square root of n2.

Also, it is better to save the result in a file rather than display it on a screen. This
can be done by the >> operator and the file can be read in using << or the
ReadList command.


  SieveOfEratosthenes[ 1000]>> primes;


  
  primes= ReadList[ "primes", Expression];


  primes

Notice the extra set of braces around the expression. These can be removed
using the Flatten command.


  primes=Flatten[primes];
  primes[[50]]

Exercise: Write a function Sieve[n,m] to create a list of primes between n and m. To start
the sieve you will need a list of primes up to square root of m.

Up to Procedural Programming