下面的程序(在prime函数内)的运行时间是110.726383227秒
如果我运行相同的程序而不将它包装在一个函数(主要)中,它的运行时间是 222.006502634 秒
我通过将其包装在一个函数中,显着提高了性能。
还有没有可能提高这个程序的效率?
# This is a program to find sum of prime numbers till 2 billion
def prime():
import time
start_time = time.clock()
num = 2
j=1
tot_sum = 0
for num in xrange(2,2000000):
count = 0
for j in xrange(1,int(num**0.5)+1): # checking from 1 to sqrt(n)+1
if(num % j == 0):
count = count+1
if(count == 1):
tot_sum = tot_sum + num
print "total sum is %d" % tot_sum
print time.clock() - start_time, "seconds"
如果你想在没有外部库的情况下解决它,你可以做一些明显的改进:
def prime():
import time
start_time = time.clock()
tot_sum = 2
for num in xrange( 3, 2000000, 2 ):
isPrime = True
for j in xrange(3, int( num ** 0.5 ) + 1, 2 ):
if( num % j == 0 ):
isPrime = False
break
if isPrime:
tot_sum = tot_sum + num
print "total sum is %d" % tot_sum
print time.clock() - start_time, "seconds"
prime()
不检查大于 2 的偶数,如果找到则不检查所有除数。您的原始代码在我的机器上运行时间为 172.924809 秒,而我的运行时间为 8.492169 秒。
如果允许使用外部库,我建议使用gmpy2
:
def prime():
from gmpy2 import is_prime
import time
start_time = time.clock()
print "total sum is %d" % (sum(filter(is_prime, xrange(3,2000000,2)))+2)
print time.clock() - start_time, "seconds"
prime()
这在 1.691812 秒内运行