Why isn't the naive PRIMES algorithm in P?

Question

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?

Answer 1

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.