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 ]
 Graham Cooper Posts: 4,043 Registered: 5/20/10
Re: Is there a polynomial time algorithm for enumerating prime numbers?
Posted: Jun 6, 2012 12:13 AM

On Jun 5, 7:37 pm, "Peter Percival" <peterxperci...@hotmail.com>
wrote:
> 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.
>

usually you can put

STEP++

in the innermost loop.

it is the SHAPE of the amount of operations as the input size
increases.

e.g. 2 nested loops is usually O(n^2)
3 nested loops is usually O(n^3)

by POLYNOMIAL TIME to FIND A PRIME

we are talking about the SIZE OF INPUT
not the size of the prime.

p=123? input size=3
p=123456789? input size=9

Rabin has a probabilistic method that was polynomial.

i.e. if p=1000
there are only half a dozen FACTORS that prove compositeness
but there are atleast 500 WITNESSES to compositeness

so each repetition you take a random stab between 1 and p
and test if it proves compositeness

SO
1 repetition - p is prime with Probability = 50%
2 repetitions - p is prime with Probability = 75%
....
100 repetitions - p is prime with Probability
99.99999999999999999999999999999999999999999999999999%

but there is an ACTUAL POLYNOMIAL Algorithm that works since Rabin,
only since 90s I think.

Her

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