<分区>
我今年 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 编写阿特金筛算法对我来说是一个相当大的挑战。
我希望那里的谷歌黑客能帮助我完成这样的事情:(