python - Python 需要很长时间才能执行代码

Question

我正在使用 PyCharm 社区 2018。我试图找到从 1 到 200 万的素数之和，这是我的代码。

primes = [x for x in range (1,2000000) if all (x%y!=0 for y in range (2,x))]
total = 0
for x in primes:
    total = total + x
print (total)

已经20分钟了，我仍然没有输出。你有什么建议让它运行得更快还是我的方法错了？

标签： pythonperformanceexecution

Answer 1

这很可能是因为您查找素数的方法效率低且范围太大。

您的算法是查找素数的蛮力方法，其时间复杂度为 O(n²)。如果您为较小的数字计时您的算法，您会发现随着 增加n，所用时间不会线性增加，而是实际上是二次的。

+--------+---------------+
|   n    | time(in sec)  |
+--------+---------------+
| 1000   |  0.007979     |
| 2000   |  0.038865     |
| 5000   |  0.137037     |
| 10000  |  0.499688     |
| 20000  |  1.892315     |
| 50000  |  10.29843     |
| 100000 |  1374.101     |
| ...    |  ...          |
+--------+---------------+

我建议你看看埃拉托色尼筛。如果你搜索它，你会发现它的许多实现，无论你想要什么语言。