失败的质数检查器

Question

这似乎是一个正常的代码并且运行良好，但是无论出于何种原因，当我尝试输入这个数字 = 18765411123451 时，计算机似乎死机了，有什么线索吗？

num = 18765411123451

if num > 1:
  for i in range(2,num):
    if num % i == 0:
      print(num,"is not a prime number")
      print("Because", i,"x",num//i, "=" ,num)
      break
  else:
    print(num,"is a prime number")
else:
  print(num,"is not a prime number")

我已经尝试了许多其他数字，除了那个数字之外，代码可以正常工作。这里发生了什么？

Answer 1

它卡住了，因为你的数字太高了。

原因是 for i in range(2,num): 和 num = 18765411123451 是 100 万亿...

再加上 python 2 将尝试分配该内存只是为了创建列表以对其进行迭代（在这种情况下使用 xrange）

好消息：您不必检查数字本身，只需检查直到平方根（包括在内）：

for i in range(2,int(num**0.5)+1):

这更合理（少于 500 万次迭代）并且会提供相同的结果。

超过一个数的平方根，如果你还没有找到除数，你就不会找到任何之后（如果q是num的约数，那么p*q == num 所以 p 或 q 必须小于或等于 num

的平方根

失败的质数检查器

A prime number checker that fails

python

numbers

calculation