如果希望所有质数都达到2000000,则应考虑使用Eratosthenes筛网
[我在python上编写了此代码段,以解决项目Euler问题#10,但我已经等了15分钟(运行此代码),但仍未结束。
请帮助我改进或优化此代码。
这是代码段:
def prime (n):
f = 1 #flag
for i in range(2,n):
if n % i == 0:
f = 0
return f
s = 0 # Sum
for i in range(2,2000000):
if prime(i) == 1:
s = i + s
print s
import math
def prime (n):
for i in xrange(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
s = 2 # Sum
for i in xrange(3,2000000, 2):
if prime(i):
s += i
print s
对我来说,运行时间不到10秒。
首先,一旦发现数字,您想从prime
返回。]
第二,您不想检查偶数。用xrange(3,2000000, 2)
跳过它们>
第三,不需要检查2
中从n
到prime
的所有数字,因为a*b = b*a
由于您使用的是Python 2,所以我已将range
替换为xrange
,效率会更高。
如果希望所有质数都达到2000000,则应考虑使用Eratosthenes筛网
python中的代码:-
def eratosthenes2(n):
multiples = set()
for i in range(2, n+1):
if i not in multiples:
yield i
multiples.update(range(i*i, n+1, i))
print(list(eratosthenes2(2000000)))
def prime_nums(N):
B = []
A = [True] * N
A[0] = A[1] = False
for k in range(2, N):
if A[k]:
for m in range(2*k, N, k):
A[m] = False
for k in range(N):
if A[k]:
B.append(k)
print(sum(B))
它也很好用。
如果希望所有质数都达到2000000,则应考虑使用Eratosthenes筛网
def prime_nums(N):
B = []
A = [True] * N
A[0] = A[1] = False
for k in range(2, N):
if A[k]:
for m in range(2*k, N, k):
A[m] = False
for k in range(N):
if A[k]:
B.append(k)
print(sum(B))