
{ sieve of Eratosthenes -- a brute force method of finding prime numbers }
{
the basic idea:
make a large set of numbers (1 .. PrimeLimit here) and
remove all the numbers that are not prime.

  take the first prime number, ie 2, and remove every second number from the set
  now all primes up to 4 (2*2) have been discovered.
  the next prime is 3, remove all multiples of 3.
  all primes up to 9 (3*3) have been discovered.
  skip 4, because it isn't a prime and has been removed from the set
  take the 5 and now remove every 5th number.
  etc....
  optimise by stopping at the sqrt of the limit and
  remove numbers starting at the square of the prime just found.
}
{$d- disable dubugging, so it runs faster}
program sieve(output);
 
const
  PrimeLimit     = 50000;

var
  primes: set of 1 .. PrimeLimit;
  i, k, n, width: integer;

begin

  primes := [2 .. PrimeLimit];

  { calculate the primes }
  for i := 1 to trunc(sqrt(PrimeLimit)) do begin
    if i in primes then begin
      k := sqr(i);
      while k <= PrimeLimit do begin
        primes := primes - [k];
        k := k + i
      end;
    end
  end;


 { find space needed to print the numbers }
 width := 1;
 i := 10;
 while i < PrimeLimit do begin
    width := width+1;
    i := 10*i;
 end;

 { output the primes in lines of 10 numbers }
 n := 0;
 for i := 1 to PrimeLimit do
   if i in primes then begin
     if n mod 10 = 0 then
       writeln
     else
       write(', ');
     write(i:width);
     n := n+1;
   end;
   writeln;
   writeln( n:1, ' primes found' );
end.

