坚持运行模式Jupyter笔记本

Question

每当我使用以下代码运行shell时，我的Jupyter Notebook就会陷入运行模式：

def is_prime(num):
    if num < 2:
        return False  
    for x in range(2, num - 1):
        if num % x == 0:
            return False  
    return True  

prime_list = []    
num = 2

while True:    
    if is_prime(num):
        prime_list.append(num)
    num += 1
if len(prime_list) == 10002:
    break


print(prime_list[-1])    

有人可以在他们的计算机上运行此代码并告诉我输出是什么？我真的很感激任何答案。

Answer 1

您的代码被卡住了，因为您的主要测试功能变得非常慢！

我运行了你的代码，找到了100,1000,2000和4000个素数的不同停止点。运行时间分别为0.01,0.23,0.98和4.31秒。

您可以看到，将要素的数量加倍，以便（大致）将所需的时间量增加四倍。这是有道理的，因为要测试n是否为素数，你必须检查它与n-2其他数字（你排除1和n）。所以，你的算法有一个至少time complexity的O(n^2)来找到n素数。

（另外，在30秒内找到10002个素数后，我得到了104759。我最初不小心输入了“100002”，它运行了很长时间没有任何结果...）