任何人都可以教我如何进一步优化这种'打印到第n个素数'脚本吗？

Question

我是一个17岁的孩子,在Python编程语言的帮助下开始编程.

我一直在寻求优化这个算法,可能是通过消除其中一个循环,或者用更好的测试来检查质数.

尝试计算并显示100000个素数时,脚本暂停约6秒,因为它在素数列表作为输出返回到控制台之前用素数填充列表.

我一直在尝试使用

print odd,

简单地打印每个找到的素数,对于较小的输入(如n = 1000)更快,但对于n = 1000000,列表本身打印速度要快得多(在python shell和控制台中).

也许整个代码/算法应该进行修改,但脚本应保持基本相同:用户键入要打印的素数(n),脚本返回所有素数直到第n个素数.

from time import time
odd = 1
primes = [2]
n = input("Number of prime numbers to print: ")
clock = time()
def isPrime(number):
    global primes
    for i in primes:
        if i*i > number:
            return True
        if number%i is 0:
            return False
while len(primes) < n:
    odd += 2
    if isPrime(odd):
        primes += [odd]
print primes
clock -= time()
print "\n", -clock
raw_input()

我可能想重写整个剧本,使用像阿特金筛子一样的筛子:http://en.wikipedia.org/wiki/Sieve_of_Atkin

但是,我只是Python的初学者(甚至是编程:我在两周前才开始编写代码),如果想弄清楚如何在Python中编写Sieve of Atkin算法,那将是一个很大的挑战.

我希望那里的谷歌黑客会通过这样的东西抓住我:(

Answer 1

一种简单的优化，无需完全破解代码即可应用。

• 随着列表变长，每个素数上的 i*i 都会变得非常浪费。相反，在循环外计算 i 的平方根，并在循环内对该值进行测试。

然而，平方根本身就是昂贵的计算，并且大多数候选数将被拒绝，因为可以被较低素数之一（3,5,7）整除，因此这并不是一个很好的优化（悲观化？）。但我们实际上并不需要那么精确，简单地检查素数是否小于该值的三分之一具有类似的效果，而无需平方根计算的计算成本，但是，以相对较少的不必要的代价为代价测试。