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).