我正在学习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中？
谢谢：）
最佳答案
算法是否为多项式时间取决于输入的表示形式例如，大数9223372036854775807适合64位无符号类型aks结果的意义在于它是位数（例如64）的多项式，而不是数本身（例如9223372036854775807）。
关于algorithm - P中的质数-运行到sqrt怎么样？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25341699/