Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Is there a polynomial time algorithm for enumerating prime numbers?
Replies: 10   Last Post: Jun 6, 2012 9:53 PM

 Messages: [ Previous | Next ]
 gnasher729 Posts: 329 Registered: 10/7/06
Re: Is there a polynomial time algorithm for enumerating prime numbers?
Posted: Jun 5, 2012 5:49 PM

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

Date Subject Author
6/5/12 Peter Percival
6/5/12 Pubkeybreaker
6/5/12 Peter Percival
6/5/12 Pubkeybreaker
6/5/12 quasi
6/6/12 Brian Q. Hutchings
6/5/12 gnasher729
6/5/12 Pubkeybreaker
6/5/12 Timothy Murphy
6/5/12 Peter Percival
6/6/12 Graham Cooper