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


Let p_n be the nth prime number (p_1 = 2, etc). Is there a polynomial P(n), and an algorithm to find p_n in a number of steps* S(n), where S(n) is bounded by P(n)?
* A step being what? If I were to write a program to implement such an algorithm, I would take "step" to mean "machine code instruction"; but there might be a better definition not tied to any particular way of implementing algorithms.
 Using Opera's revolutionary email client: http://www.opera.com/mail/

