algorithm - P 中的素数 - 跑到 sqrt 怎么样？

Question

我正在学习P和NP。
我读过确定给定数字是否为素数的问题是 P 中的一个问题，这意味着它具有解决它的多项式时间算法。
我还读到这一事实在 2002 年被 AKS 算法证明。

众所周知，我们可以通过运行直到其平方根来确定特定数字是否为素数。

伪代码：

isPrime(N):

sqrt(N) <- squareRoot(N)

for i from 2 to Sqrt(N)
    if (n mod i == 0)
        return false
return true

我的问题很简单：
为什么上面的算法不能证明这个问题在 P 中？
谢谢 ：）

Answer 1

算法是否是多项式时间取决于输入的表示。例如，大数 9223372036854775807 适合 64 位无符号类型。AKS 结果的意义在于它是位数的多项式（例如，64）而不是数字本身（例如，9223372036854775807）。