|
|
Is there a polynomial time algorithm for enumerating prime numbers?
Posted:
Jun 5, 2012 5:37 AM
|
|
Let p_n be the n-th 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/
|
|
