我正在尝试完成Project Euler挑战：
通过列出前六个素数：2,3,5,7,11和13，我们可以看到第6个素数是13。
什么是10 001主数？
我的代码似乎是正确的，因为它适用于小数字，例如6th prime是13。
我如何改进它，以便代码将更快地运行更大的数字，如10 001。
代码如下：
#Checks if a number is a prime
def is_prime(n):
count = 0
for i in range(2, n):
if n%i == 0:
return False
break
else:
count += 1
if count == n-2:
return True
#Finds the value for the given nth term
def term(n):
x = 0
count = 0
while count != n:
x += 1
if is_prime(x) == True:
count += 1
print x
term(10001)
更新：
谢谢你的回复。我应该更清楚，我不是要加速翻译或找到更快的解释器，因为我知道我的代码不是很好，所以我正在寻找使我的代码更有效的方法。
需要思考的几个问题：
import math
count = 0 <br/> def is_prime(n):
if n % 2 == 0 and n > 2:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
for i in range(2,2000000):
if is_prime(i):
count += 1
if count == 10001:
print i
break
我以不同的方式接近它。我们知道2的所有倍数都不是素数（2除外）我们也知道所有非素数都可以分解成素数。
即
12 = 3 x 4 = 3 x 2 x 2
30 = 5×6 = 5×3×2
因此，我遍历一个奇数列表，累积一个素数列表，并且只尝试在此列表中找到具有素数的奇数的模数。
#First I create a helper method to determine if it's a prime that
#iterates through the list of primes I already have
def is_prime(number, list):
for prime in list:
if number % prime == 0:
return False
return True
编辑：最初我是递归写的，但我认为迭代的情况要简单得多
def find_10001st_iteratively():
number_of_primes = 0
current_number = 3
list_of_primes = [2]
while number_of_primes <= 10001:
if is_prime(current_number, list_of_primes):
list_of_primes.append(current_number)
number_of_primes += 1
current_number += 2
return current_number
不同的快速Python解决方案：
import math
prime_number = 4 # Because 2 and 3 are already prime numbers
k = 3 # It is the 3rd try after 2 and 3 prime numbers
milestone = 10001
while k <= milestone:
divisible = 0
for i in range(2, int(math.sqrt(prime_number)) + 1):
remainder = prime_number % i
if remainder == 0: #Check if the number is evenly divisible (not prime) by i
divisible += 1
if divisible == 0:
k += 1
prime_number += 1
print(prime_number-1)
基于论文中的haskell代码：The Genuine Sieve of Eratosthenes by Melissa E. O'Neill
from itertools import cycle, chain, tee, islice
wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
def spin(wheel, n):
for x in wheel:
yield n
n = n + x
import heapq
def insertprime(p,xs,t):
heapq.heappush(t,(p*p,(p*v for v in xs)))
def adjust(t,x):
while True:
n, ns = t[0]
if n <= x:
n, ns = heapq.heappop(t)
heapq.heappush(t, (ns.next(), ns))
else:
break
def sieve(it):
t = []
x = it.next()
yield x
xs0, xs1 = tee(it)
insertprime(x,xs1,t)
it = xs0
while True:
x = it.next()
if t[0][0] <= x:
adjust(t,x)
continue
yield x
xs0, xs1 = tee(it)
insertprime(x,xs1,t)
it = xs0
primes = chain([2,3,5,7], sieve(spin(cycle(wheel2357), 11)))
from time import time
s = time()
print list(islice(primes, 10000, 10001))
e = time()
print "%.8f seconds" % (e-s)
打印：
[104743]
0.18839407 seconds
from itertools import islice
from heapq import heappush, heappop
wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,
4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
class spin(object):
__slots__ = ('wheel','o','n','m')
def __init__(self, wheel, n, o=0, m=1):
self.wheel = wheel
self.o = o
self.n = n
self.m = m
def __iter__(self):
return self
def next(self):
v = self.m*self.n
self.n += self.wheel[self.o]
self.o = (self.o + 1) % len(self.wheel)
return v
def copy(self):
return spin(self.wheel, self.n, self.o, self.m)
def times(self, x):
return spin(self.wheel, self.n, self.o, self.m*x)
def adjust(t,x):
while t[0][0] <= x:
n, ns = heappop(t)
heappush(t, (ns.next(), ns))
def sieve_primes():
for p in [2,3,5,7]:
yield p
it = spin(wheel2357, 11)
t = []
p = it.next()
yield p
heappush(t, (p*p, it.times(p)))
while True:
p = it.next()
if t[0][0] <= p:
adjust(t,p)
continue
yield p
heappush(t, (p*p, it.times(p)))
from time import time
s = time()
print list(islice(sieve_primes(), 10000, 10001))[-1]
e = time()
print "%.8f seconds" % (e-s)
打印：
104743
0.22022200 seconds
import time
from math import sqrt
wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
list_prime = [2,3,5,7]
def isprime(num):
limit = sqrt(num)
for prime in list_prime:
if num % prime == 0: return 0
if prime > limit: break
return 1
def generate_primes(no_of_primes):
o = 0
n = 11
w = wheel2357
l = len(w)
while len(list_prime) < no_of_primes:
i = n
n = n + w[o]
o = (o + 1) % l
if isprime(i):
list_prime.append(i)
t0 = time.time()
generate_primes(10001)
print list_prime[-1] # 104743
t1 = time.time()
print t1-t0 # 0.18 seconds
打印：
104743
0.307313919067
Project Euler的目的不是考虑学习编程，而是考虑算法。在问题＃10上，你的算法需要比＃7等更快。所以你需要找到一种更好的方法来查找素数，而不是更快的方式来运行Python代码。人们通过考虑数学来解决这些问题，而这些问题是你现在使用的计算机速度要慢得多。
在那个问题上，如果你真的需要帮助来思考这个问题，也许可以询问https://math.stackexchange.com/上的素数算法。
更快的解释器不会削减它。即使用C语言或汇编语言编写的实现也不够快（在项目Euler的“大约一秒钟”时间范围内）。坦率地说，你的算法是可悲的。一些研究和思考将帮助你编写一个算法，它在狗慢解释器中运行速度比在本机代码中实现的当前算法更快（我不会说出任何具体细节，部分原因是因为这是你的工作，部分是因为我无法分辨需要多少优化）。
许多欧拉问题（包括这个问题）都设计成一个解决方案，可以在几乎任何给定的硬件和编译器上计算可接受的时间（好吧，不是PDP-11上的INTERCAL）。
您的算法有效，但它具有二次复杂性。使用更快的解释器将为您提供线性性能提升，但在计算10,000个素数之前，二次复杂性将使它相形见绌。算法的复杂度要低得多;找到他们（或谷歌他们，没有羞耻，你仍然会学到很多）并实施它们。
在没有讨论你的算法的情况下，PyPy解释器可以比普通的CPython解释器更快，因为这样可以进行严格的数值计算。你可能想尝试一下。
检查你不必运行的素数，直到n-1或n / 2 ....
要更快地运行它，您只能检查直到n的平方根
这是我所知道的最快的算法
def isprime(number):
if number<=1:
return False
if number==2:
return True
if number%2==0:
return False
for i in range(3,int(sqrt(number))+1):
if number%i==0:
return False
return True
正如大多数人所说，所有这些都是为了提出正确的算法。你考虑过看看Sieve of Eratosthenes吗？
import time
t=time.time()
def n_th_prime(n):
b=[]
b.append(2)
while len(b)<n :
for num in range(3,n*11,2):
if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
b.append(num)
print list(sorted(b))[n-1]
n_th_prime(10001)
print time.time()-t
版画
104743
0.569000005722秒
一个pythonic答案
import time
t=time.time()
def prime_bellow(n):
b=[]
num=2
j=0
b.append(2)
while len(b)-1<n:
if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
b.append(num)
num += 1
print b[n]
prime_bellow(10001)
print time.time()-t
打印
104743
0.702000141144 second