# Time Complexity of Basic Primality Test Algorithm [duplicate]

The algorithm I'm referring to is one of the most fundamental primality checks: For a number, $n$, check if it is divisible by some odd number, $k$, less than or equal to $\sqrt{n}$. Assume $n$ is a fixed size and that all basic arithmetic operations (add, subtract, multiply, divide, remainder) run in $O(1)$. I don't see why this algorithm will not be $O(\sqrt{n})$, but apparently it's not since PRIMES was considered an NP problem up until the AKS primality check.

The problem with your statement is that you assume that all the basic arithmetic operations are $O(1)$ and that the amount of numbers you will have to check is $O(\sqrt{n})$, relative to the size of the input.
This is wrong because $\text{PRIMES}$ is the language of all the prime numbers, given in a binary format. So an input of length $n$ will be a number of size $O(2^n)$. Then, if the input is some number $x$, in order to check all the numbers up to $\sqrt x$ you will have to go over $O(\sqrt{2^n})$ numbers, which is $O(2^{n/2})$ numbers. Even with $O(1)$ operations this will not take a polynomial amount of time.
• Ah, so $n$ has to be the actual size of the input, not the input itself? – Badr B Jun 2 '18 at 8:51