In article <1110724959.904728.143940@l41g2000cwc.googlegroups.com>,
<jstevh@msn.com> wrote:

Christian Bau wrote:

In article <1110666370.073219.299350@f14g2000cwb.googlegroups.com>,
jstevh@msn.com wrote:

<snipped ***** explanation why Harris' method is different from
Legendre's Formula>

Notice the emotion and the heat of that emotion.

Just go to

http://mathworld.wolfram.com/LegendresFormula.html

Between equation (1) and (2) you find

"Taking a = pi (sqrt (x)), where pi (n) is the prime counting
function, gives phi (x, pi (sqrt (x))) = pi (x) - pi (sqrt (x) +

1..."

and equation (3) is the recurrence relation

"phi (x, a) = phi (x, a-1) - phi (x / p (a), a-1)"

However, I can explain by example, and then you can go to that site and
see the truth.

The sci.math'er who made that reply has lied about my work for over two
years now, and his energy in replying as much as he does to keep up his
position should tell you something.

Here's another example, and then you can go to the link he mentioned
and see if there's anything like it.

Counting up to 50 this time, my idea first gets the even composites:

4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38,
40, 42, 44, 46, 48, 50

and then gets the *odds* that have 3 as a factor:

9, 15, 21, 27, 33, 39, 45

where notice I don't bother with evens that have 3 as a factor, and
then you get the odds that don't have 3 as a factor that do have 5:

25, 35

and that leaves composites that have 7 as a factor, but none of the
smaller primes, where there is just one:

49

and notice that you have a rapidly shrinking count, from a sensible way
to count primes.

Without further comment I post a small program in Pascal that
is on my site since 1995
http://home.hccnet.nl/a.w.m.van.der.horst/pipi.pas
The algorithm is again similar but not quite Legendre method.
DismissedBy(n,p) = Dleg(n,p) - Dleg(n,p-1)

Like the real mathematicians have pointed out, if you are serious
about prime counting you should supplement this with a sieve to
find the small primes.

I think it is a nice little program, but no reason for megalomanic
claims, or even a publication in print.

The explanation is more lucid then James's.

------------------------------------------------------

{ 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

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

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.
------------------------------------------------------

James Harris

--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.