python - Python中素数查找算法的运行时间

Question

问题:

我有以下任务:

[...] write a program that receives a positive integer greater than 1 and verifies whether it is prime or composite.

解决方案:

我想出了以下内容:

n=int(input())
flag=True
for i in range(2,n//2+2):
    if n%i==0:
        print("Not prime.")
        flag=False
        break
if flag==True:
    print("Prime.")

这似乎是正确的。然后，我决定试一试，看看用大整数输入会如何， 10^9+7 看起来是个不错的选择。但是，程序似乎根本没有运行完，一直运行了 30 多秒，直到我决定将其杀死。

但是，考虑到算法中的循环最多运行 ~ 5*10^8 时间，并考虑到现代计算机可以在一秒钟内执行的大量计算，运行时间不是不成比例地长吗？

这里发生了什么？

是否 10^9+7 作为 int 的“上限”工作在 Python 中和在 C 中一样键入计算，从而以某种方式“溢出计算”？还是我的算法有问题？

提前致谢!

Answer 1

当然，在 Python 这样的解释型语言中，事情会更慢——与等效的 C 实现相比，有时您可能会损失一到两个数量级的性能。但是，您的算法渐进地比必要的差得多。你的算法是O(n) ，但仅通过检查直到 n 的平方根的可分性，你可以达到O(sqrt(n))时间。您还可以通过实现车轮分解来通过一些恒定因素来加快速度。轮子 {2, 3}和 {2, 3, 5}是相当普遍的，但是当您向轮子添加更多素数时，您会得到递减的 yield 。使用 {2} 让事情变得简单轮子，我们可以跳过所有偶数(除了 2)，因为它们都不是素数。

def is_prime(n):
    if n < 3:
        return n == 2
    if not n % 2:
        return False

    for i in range(3, int(n ** 0.5) + 2, 2):
        if not n % i:
            return False
    return True