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分钟了，还是没有输出。您有什么建议可以使它运行更快，还是我的方法有误？

Answer 1

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

您的算法是一种寻找素数的蛮力方法，time complexity 是 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     |
| ...    |  ...          |
+--------+---------------+

如果您要搜索此内容，我建议您使用您想要的任何语言查看 Sieve of Eratosthenes. You will find many implementations。

Answer 2

您的代码是正确的。有很多方法可以获取所有质数，而您使用的是最基本的定义，这就是您的代码运行缓慢的原因。你可以参考这个post（有很多方法可以得到所有素数，而你使用的是最基本的定义，这就是为什么你的代码很慢。你可以参考这个post Fastest way to list all primes below N 到 ) 以获得更高级和更有效的计算素数的方法，这应该会大大加快您的代码速度。虽然你需要学习和理解很多数学原理和细节。

Answer 3

我建议使用多处理来加速您的代码

from multiprocessing import Pool
def find_prime(n):
    #code to determine prime number here
    #return 0 if it is not prime or the number if it is

pool=Pool()
total=sum(pool.map(find_prime,range(1,2000000))

Python 执行代码需要很长时间

Python is taking a very long time to execute code

python

performance

execution