3
$\begingroup$

The naive algorithm tries dividing $n$ by $2 \dots n-1$ to see if it divides without a remainder. Each division can be done in $O(n)$-time and there are $O(n)$ divisions to be made. What's wrong with this algorithm, or rather why is it not in $P$ complexity?

$\endgroup$

1 Answer 1

9
$\begingroup$

Primality testing algorithms have their complexity measured as the number of digits grows to infinity, not the size of the integer itself. Given an integer $N$ with $n$ digits, so that $N\approx 10^n$, the algorithm you gave above grows exponentially in $n$, the number of digits.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .