Re: Mystery rejection, 3-d prime counting function
From: Christian Bau (christian.bau_at_cbau.freeserve.co.uk)
Date: 06/26/04
- Next message: MorituriMax: "Re: This should be a no brainer but.."
- Previous message: MorituriMax: "Re: Math, Physics, and the direction of time"
- In reply to: matt grime: "Re: Mystery rejection, 3-d prime counting function"
- Next in thread: Kenneth Doyle: "Re: Mystery rejection, 3-d prime counting function"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 26 Jun 2004 19:19:58 +0100
In article <f9a5a56b.0406261002.6a797c97@posting.google.com>,
mattgrime@o2.co.uk (matt grime) wrote:
> I just googled for prime counting function, and no mention of you came
> up. In fact apart from *the* prime counting function the following
> hits came up on the first page:
>
> Legendre's formula, Lehmer's formula, Mapes' method, Meissel's
> formula....
>
> legendre's formula, and setting one variable to sqrt(x), looks exactly
> the same as yours, and is noted to be a very inefficient way of
> counting primes.
I wouldn't exactly put it like that. The straightforward method (apart
from checking each number in turn for primality and counting the ones
which are primes, which would be downright stupid) would be to create a
huge sieve of the primes and count them. Legendre's formula effectively
calculates how many composite numbers you remove from the sieve while
avoiding the work of creating the sieve and actually removing the
composite numbers, so it is a significant step forward. Faster than
doing a sieve by a huge constant factor.
So it is not really inefficient, it is just very inefficient compared to
other methods that had 200 years to improve on it. The improved methods
still use exactly the same formula, they just use sieves in increasingly
clever ways to find many of the intermediate results that are needed.
And one of the first attempts of Harris tested whether n was prime by
comparing pi (n) and pi (n-1). If you do that often enough, then you get
something that is _really_ inefficient.
> I don't think anyone doubts you have something that counts primes,
> just something not very efficient or original. Are you about to cry
> wolf again?
- Next message: MorituriMax: "Re: This should be a no brainer but.."
- Previous message: MorituriMax: "Re: Math, Physics, and the direction of time"
- In reply to: matt grime: "Re: Mystery rejection, 3-d prime counting function"
- Next in thread: Kenneth Doyle: "Re: Mystery rejection, 3-d prime counting function"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
