如何使此代码在python上运行得更快?

问题描述 投票:2回答:3

[我在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
python performance helpers
3个回答
4
投票
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中从nprime的所有数字,因为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)))

来源-http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

http://en.wikipedia.org/wiki/Sieve_of_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))   

它也很好用。


1
投票

如果希望所有质数都达到2000000,则应考虑使用Eratosthenes筛网


0
投票
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))   
© www.soinside.com 2019 - 2024. All rights reserved.