Re: Prime Numbers Algorithms

From: Paul Hsieh (qed_at_pobox.com)
Date: 03/07/04 

Date: 6 Mar 2004 23:13:24 -0800

James Rogers <jimmaureenrogers@att.net> wrote:
> CBFalconer <cbfalconer@yahoo.com> wrote:
> > You snipped the final paragraph of my post, which said:
> >
> >> To find the Nth prime I would suggest using one of the
> >> approximations to select the range to check, and then executing
> >> such a sieve.
> >
> > The code can easily be altered to stop dead on the Nth prime. The
> > only real problem is to determine the size of the sieve, which
> > depends on the Nth prime! However the sieve size only needs to be
> > sufficient, not exact.
> >
> > I thought the purpose of the exchange was the speed of the
> > algorithms. I think I showed that the sieve would be faster, or
> > at least of the same order.
>
> I agree that a seive is faster. I do not understand how one chooses
> the proper range for an Nth parameter entered from the command line.

Sieves are faster until you start traversing your swap space just
trying to fill it in. Sieve algorithms are inherently non-scalable.
Using a bit array and skipping even numbers, the best you can do is
256MBs to cover the entire 2^32 space. There's no way you could fill
in such an array (roughly 128million times) in reasonable time.
 
> Of course one could choose a range that goes from 2 through the upper
> bounds of an integer as a native data type. Is this what you suggest?
>
> The algorithm I chose determines the first N primes and prints the Nth.
> Is there a way to determine the Nth prime (when N is known only at
> run-time) without also determining all the primes preceding the Nth
> prime?

There actually is such an estimation function:

    Prime(n) ~= n * log (n)

You can check this estimation yourself -- its not too terrible.
 
> The algorithm I used is a modified sieve. Each new number is tested
> for prime-ness using only known prime numbers less than the square
> root of the current candidate for prime-ness.

So its a division test nevertheless. This means your prime test
algorithm is going to be O(sqrt(n)) no matter what.
 
> The 100000th prime number is 1299709. This number is clearly outside
> the range of 2 through 100000.

I got 1299674. Of course the 10000000th (10 millionth) prime is
179422572 which I was able to determine in 153 seconds on my 1.7Ghz
Athlon because I use a somewhat more scalable algorithm. :)
 
> As far as timing calculations, finding all the prime numbers less than
> 1000 takes my program (and computer) 0.0015 seconds. 997 is the 168th
> prime number. On the other hand, the 1000th prime number is 7919 and
> takes my system 0.025 seconds to find.
>
> Clearly, the farther down the list of prime numbers we go, the more
> sparse they are along the number line, making my approach non-linear
> in time. By that I mean that, as shown above, the 1000th prime takes
> about 20 times as much time as the 168th prime. The time growth is
> clearly non-linear.

The algorithm I posted has essentially constant running time. (I.e.,
determining the nth prime will still take roughly linear time.)

I have not studied the problem of determining the nth prime number
that deeply, but it seems to me that if you have a lot of offline
time, you could precalculate an array to map n to the (1<<n)th prime.
Then when called you could do a binary search into this array to know
where you should start counting from. On average this would only save
you 25% of the time, but by making the array denser (say 1024 entries
spaced by factors of 2^(1/32) apart) you could save almost 98% of your
running time (not bad -- it'll buy you an order of magnitude, anyway.) 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://www.pobox.com/~qed/32p.c

Relevant Pages

  • Re: prime number function
    ... this would be OK as an algorithm. ... generates every possible permutation? ... > You can also find the Nth prime using a gold compass. ...
    (sci.math)
  • Re: Prime Numbers Algorithms
    ... >> such a sieve. ... > The code can easily be altered to stop dead on the Nth prime. ... The algorithm I chose determines the first N primes and prints the Nth. ... numbers from a pre-determined pool of prime numbers. ...
    (comp.programming)
  • Re: What cent values are possible with only two coins?
    ... integer linear combination of A and B; there is an algorithm. ... Given that there's even a gawdawful "formula" (involving floors ... and goodness knows what else) for the nth prime as a function of n, ...
    (sci.math)
  • Re: Standard Model of N means standard well-ordering ?
    ... >> algorithm to ascertain the value of the nth prime, ... Now formally speaking, we have ...
    (sci.logic)
  • Re: getting nth prime
    ... with limits and gross generalizations. ... algorithm that returns the Nth prime number which is based on the trial ... division method and not some kind of sieve ... ... Eratosthenes to find the Nth prime number? ...
    (sci.crypt)