0
$\begingroup$

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.

$\endgroup$

marked as duplicate by Community Jun 2 '18 at 16:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ah, so $n$ has to be the actual size of the input, not the input itself? $\endgroup$ – Badr B Jun 2 '18 at 8:51
  • 1
    $\begingroup$ @BadrB exactly :) $\endgroup$ – Mickey Jun 2 '18 at 12:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.