Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Pubkeybreaker

Posts: 1,394
Registered: 2/12/07
Re: Is there a polynomial time algorithm for enumerating prime numbers?
Posted: Jun 5, 2012 6:37 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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


Use binary search on pi(n), assuming that one can compute pi(n) in
Polylog time.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.