Re: getting nth prime

"Francois Grieu" <fgrieu@xxxxxxxxxxxx> wrote in message
news:fgrieu-CFE5AA.07244525042006@xxxxxxxxxxxxxxxxxxxxxx
To the question
Is there an algorithm other than Eratosthene Sieve to find the Nth
prime number

In article <8Of3g.69272$H71.28527@xxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Joseph Ashwood" <ashwood@xxxxxxx> wrote:

There are variations of counting and seiving, probably hundreds of
them throughout the years, but it currently appears that there is
no way to find the n-th prime number without knowing the n-1th prime
number (except for directly sievable values). More specifically it
appears to be impossible to resolve n to an integer without knowing
either the n-1th or n+1th prime (e.g if I know 5 is the third prime
I can figure out that 7 is the fourth, if I know 11 is the 5th prime
I can figure out 7 is the fourth).

The above I think can't be reconciled with results on Pi(x), the
prime-counting function. To compute the Nth prime, we can find
x such that Pi(x) is close to N, compute Pi(x) exactly, then move
from here sequentially. Computing Pi(x) exactly is fast, a day
or so is enough to determine that the 2220819602560918841 th prime
is 100000000000000000039.

I see where my error is, if we know the number of primes <= k +/- 1 we can
resolve n (where k is the nth prime), otherwise we have to determine the
count. My main point though was that a count or sieving of some kind is
necessary to perform, even though we have hundred of variations (no
citation, just a guess) throughout the centuries.
Joe


.

Relevant Pages

  • Re: Outlook 2002 not retaining password
    ... You cannot fix it. ... that'll be why I've been unable to resolve it then! ... Knowing what the problem is helped me Google the right issue and there ...
    (microsoft.public.outlook.general)
  • Re: why vista have many compatiblity issues?
    ... almost of my favorites applications are not installe? ... Can Someone resolve this matter? ... Probably not without knowing what programs, ...
    (microsoft.public.windows.vista.general)
  • Re: server urls for windows update
    ... using Microsoft Update) ... Knowing your target may help ... others in helping you to resolve your problem. ...
    (microsoft.public.windowsupdate)
  • Re: getting nth prime
    ... no way to find the n-th prime number without knowing the n-1th prime ... prime-counting function. ... To compute the Nth prime, ... Computing Piexactly is fast, ...
    (sci.crypt)