python - 素数生成器优化(欧拉计划 #7)

Question

我想优化这段代码，以便完成此任务的时间更短(我确实希望一路打印所有质数):

(获取第10001个素数)

counter = 10001
target_num = 1          #because if we add 1 to it the first time, it will become 2
input('This may take a while, press Enter to continue; you can stop the program any time by pressing CTRL + C.')
while counter <= 10001 and counter > 0:
    target_num = target_num + 1
    for x in range(1, target_num + 1):
        if target_num % x == 0:
            if x == 1:
                pass
            elif x != target_num:
                break
            elif x == target_num:
                counter = counter - 1
                print (target_num)  #prints prime number so user knows if program is actually crunching numbers
print ('10001st prime number is: ' + str(target_num))

Answer 1

我为您的代码计时。这是需要多长时间:

Over 72 seconds (%timeit died, sorry!)

明显的问题是您运行从 1 到 target_num 的循环来查找素数。那是没有必要的。

证明可见 here .

这是一个计算平方根的版本。您也可以删除那些多余的 if。

def foo():
    counter = 10001
    target_num = 1          #because if we add 1 to it the first time, it will become 2
    while counter <= 10001 and counter > 0:
        target_num = target_num + 1
        for x in range(2, int(target_num ** 0.5) + 1 ):
            if target_num % x == 0:
                if x != target_num:
                    break
        else:
            counter -= 1

    print ('10001st prime number is: ' + str(target_num))

时间:

1 loop, best of 3: 442 ms per loop

可以通过将范围步进 2 来实现进一步的加速，因此您可以跳过对偶数的检查:

def foo():
    counter = 10000
    target_num = 1          
    while counter <= 10001 and counter > 0:
        target_num = target_num + 2
        ...

时间:

1 loop, best of 3: 378 ms per loop

---

脚注:此答案解释了您当前方法的不足之处。但是，对于全新的方法，请查看 Sieve of Eratosthenes - Finding Primes Python ，或@AChampion 的回答。