Python sqrt() 运行时间加倍？

Question

我最近开始学习 Python。如果这真的很明显，我深表歉意。

我正在学习 2008 年麻省理工学院计算机科学公开课，正在研究计算第 1000 个素数的问题。 Python2.7.3，Win7 lappy（咳咳……）

这是我想出的代码：

num = 3
primeList = [2]

while len(primeList) < 1000:
    for i in primeList:
        if num % i == 0:
            break
    else:
        primeList.append(num)
    num += 1

print "The 1,000th PRIME integer is", primeList[999]

其中一个分配条件是只检查奇数。考虑到起始 num 是三个，我认为将 num+=1 简单地更改为 num+=2 就足够容易了。注意：我不会用我编写的详细代码让您感到厌烦，但是在编写此代码时，我使用了一种非常冗长的模式来打印出每次检查的结果，无论它是否为质数，正在检查哪个数字，哪个如果它不是质数等，则整数除以它（再次抱歉 - newB！）

在这一点上，我开始好奇地测试这是否真的花费更少的时间来计算 - 似乎如果检查一半的数字是否优先，应该花费一半的时间，不是吗？

我导入了时间模块来检查这需要多长时间。无论哪种方式，计算到第 1000 个都非常快，所以我将搜索的素数增加到第 10,000 个，但没有发现任何显着差异。在 num+=1 和 num+=2

之间

import time
start = time.time()

num = 3
primeList = [2]

while len(primeList) < 10000:
    for i in primeList:
        if num % i == 0:
            break
    else:
        primeList.append(num)
    num += 2

print "The 10,000th PRIME integer is", primeList[9999]
end = time.time()
print "That took %.3f seconds" % (end-start)

有时 n+=2 甚至会多花几毫秒。？。我觉得这很奇怪，想知道是否有人可以帮助我理解为什么 - 或者更重要的是：如何？

此外，我接下来导入了 sqrt() 函数，认为这会减少在确认优先级之前检查的整数数量，但这使运行时间增加了一倍 =^O.

import time
start = time.time()

from math import sqrt

num = 3
primeList = [2]

while len(primeList) < 100000:
    for i in primeList:
        if i <= sqrt(num):
            if num % i == 0:
                break
    else:
        primeList.append(num)
    num += 2

print "The 100,000th PRIME integer is",primeList[99999]
end = time.time()
print 'that took', end - start, "seconds, or", (end-start)/60, "minutes"

当然 - 这可能是我编写代码的方式！如果不是，我很好奇我到底在这里调用了什么，花了这么长时间？

谢谢！

Answer 1

两件事。

首先，您要在每次循环迭代时计算 sqrt(n)。这会增加工作量，因为这是您的代码现在必须在每次循环中执行的其他操作。

其次，您使用 sqrt 的方式不会减少它检查的数字数量，因为即使 i 大于 [=11]，您也不会退出循环=].所以它一直在为所有更高的数字做一个无所事事的循环。

试试这个：

while len(primeList) < 100000:
    rootN = sqrt(num)
    for i in primeList:
        if i <= rootN:
            if num % i == 0:
                break
        else:
            primeList.append(num)
            break
    else:
        primeList.append(num)
    num += 2

这在我的机器上大约 3 秒内找到了 100,000 个素数。

Python sqrt() 运行时间加倍？

Python sqrt() doubles runtime?

python

runtime

primes