
Re: Is there a polynomial time algorithm for enumerating prime numbers?
Posted:
Jun 5, 2012 6:37 PM


On Jun 5, 5:49 pm, "christian.bau" <christian....@cbau.wanadoo.co.uk> wrote: > On Jun 5, 3:58 pm, "Peter Percival" <peterxperci...@hotmail.com> > wrote: > > > Suppose that, having read Timothy Murphy's post, I write P(log n) instead > > of P(n), is the answer still yes? > > If you had a method to calculate the nth prime in c * log (n) steps, > then I would think you would get a very very fast primality tester, c' > * log^2 (n) guaranteed, but on average a lot faster: > > Given some k such that p_k <= n <= p_(k+1), n is obviously a prime if > and only if n = p_k or n = p_k+1. > Make two educated guesses what k would be (around n / log (n), but you > can find a more precise formulas), one k that is too small, and k' > that is too big. Improve the guess repeatedly by assuming that p_n is > a linear function of n which is reasonably close to true.
Use binary search on pi(n), assuming that one can compute pi(n) in Polylog time.

