{ Copyright (c) 1995 by Albert van der Horst }

program pi;

uses Crt;

{ This program calculates how many primes there are less or equal a given
  number. This function is called pi(n).
  It only demonstrates the algorithm. The range allowed for the number `n'
  is limited by the signed integers Pascal can handle: 32675.
  It is based on a careful analysis of the Eratosthenes' sieve.
  In the sieve numbers are dismissed because they are divisible by
  prime numbers.
  We will use the notion of "dismissing by".
  A number is "dismissed by" a prime, if that prime is its smallest divider.
  The numbers smaller than or equal to `n' are divided in disjunct sets
  of numbers dismissed by a certain prime, and the number 1.
  A large primes p<=n (in fact all primes larger than sqrt(n)) form such
  a set with only one member. (The definition implies that a prime is
  dismissed by itself.)
  An example of the numbers <=17 and their dismissing primes:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
  - 2 3 2 5 2 7 2 3  2 11  2 13  2  3  2 17
  By inspection we see that Dismiss(17,3) should return 3.

}

{ IsPrime is an auxiliary function that tells whether `n' is prime.
}

Function IsPrime( n: integer):boolean;
var
  i:       integer;     { Just a counter }

begin
  IsPrime := True;
  if n>=4 then
      for i:=2 to n do
          if n/i<i then
              exit
          else if n mod i = 0 then
              begin
                 IsPrime := False;
                 exit
              end
end;

{  `DismissedBy' counts the numbers less than `n' dismissed by the prime `p'.
   See explanation at the beginning.
}
Function DismissedBy( n,p: integer):integer;
var
  nsmall:  integer;     { The amount of multiples of `p' <=n }
  p2:      integer;     { a prime smaller than `p' }
  d:       integer;     { return value, dismissed }
begin
  nsmall := n div p;
  if nsmall<p then
  begin
      DismissedBy :=1;
      exit
  end;

  { m is dismissed by p iff m div p is NOT dismissed by some p1 <p }
  { Start counting them }
  d := nsmall;  { `nsmall' multiples are all candidates }

  { Subtract all those dismissed by smaller primes }
  for p2:=2 to p-1 do
      if IsPrime(p2) then
          d := d - DismissedBy( nsmall, p2 );

   DismissedBy :=d
end;

{  Returns PI the number of primes smaller or equal to `N'
   We may count the primes < N as follows.
   Start with N-1 because all numbers except 1 could be primes.
   Subtract all those dismissed by some prime except that prime
   itself.
   We may stop the loop at sqrt(n) because from then on,
   DismissedBy(n,p2) = 1 . From then on, we subtract one but add one
   again for the prime itself, so the running total does not change.
   Alternatively you may think of dismissing as the process of sieving
   using Erathosthenes' sieve, where you may stop at the sqrt(n).

   Stopping at the root is the crux.
   You could of course just test all numbers <N for primality
   using IsPrime().
}

Function CountPr( N:integer ):integer;
   var r:integer;       { result }
   var p:integer;       { running prime }

begin
   r := N-1;   { All except one are prime candidates }

   for p:=2 to n do
      if p*p>n then
      begin
         CountPr := r;
         exit
      end
      else if IsPrime(p) then
      begin
          r := r - DismissedBy( n, p );
          r := r+1;     { Correct: the prime itself was also dismissed }
      end;

      CountPr := r;
end;

var N : integer;

begin {countpr}
  repeat
      Writeln('Give a number ...');
      read(N);
      Writeln('The number of primes <=',N,' is ',
         CountPr(N) );
  until N=0;
end.