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