用埃氏筛法筛选并输出前100w内的质数个数的两种不同的算法的性能差别
不多废话，直接上代码这个是比较快的版本，100w耗时0.07s
from time import time
def ess(n):
pl =
Td = * (n + 1)
for i in range(3, n + 1, 2):
if Td:
pl.append(i)
for j in range(i ** 2, n + 1, i * 2):
Td = False
return pl
if __name__ == "__main__":
t1 = time()
nei = 10 ** 6
pl = ess(nei)
t2 = time()
tt = t2 - t1
print("{}以内素数共{}个:".format(nei,len(pl)))
print("共耗时{}秒".format(tt))#0.7s这个是比较慢的版本，100w耗时0.10s
from time import time
def sieve(n):
prime = * (n + 1)
p = 2
while (p * p <= n):
if (prime == True):
for i in range(p * p, n+1, p):
prime = False
p += 1
for p in range(2, n):
if prime:
pl.append(p)
if __name__=='__main__':
pl=[]
n = 1000000
t1 = time()
sieve(n)
t2 = time()
tt = t2 - t1
print(n)
print("{}以内素数共{}个:".format(n,len(pl)))
print("共耗时",tt,"秒")#0.10s对算法理解比较深的朋友可以来探讨一下为什么两种相同的算法性能会有差别，怎么优化
第一种i的步长为2（只计算奇数），第二种p的步长为1；第一种j的步长为2i，第二种i的步长为p。因此第一种更为高效。 from time import time
def sieve(n):
prime = * (n + 1)
p = 3
while (p * p <= n):
if (prime == True):
for i in range(p * p, n+1, 2 * p):
prime = False
p += 2
for p in range(3, n， 2):
if prime:
pl.append(p)
if __name__=='__main__':
pl=
n = 1000000
t1 = time()
sieve(n)
t2 = time()
tt = t2 - t1
print(n)
print("{}以内素数共{}个:".format(n,len(pl)))
print("共耗时",tt,"秒")#0.10s
这样改更快一点
页:
[1]