用埃氏筛法筛选并输出前100w内的质数个数的两种不同的算法的性能差别

fjqz177

不多废话，直接上代码
这个是比较快的版本，100w耗时0.07s

1. from time import time
   
2. 
   
3. def ess(n):
   
4.     pl = [2]
   
5.     Td = [True] * (n + 1)
   
6.     for i in range(3, n + 1, 2):
   
7.         if Td[i]:
   
8.             pl.append(i)
   
9.             for j in range(i ** 2, n + 1, i * 2):
   
10.                 Td[j] = False
    
11.     return pl
    
12. 
    
13. if __name__ == "__main__":
    
14.     t1 = time()
    
15.     nei = 10 ** 6
    
16.     pl = ess(nei)
    
17.     t2 = time()
    
18.     tt = t2 - t1
    
19.     print("{}以内素数共{}个:".format(nei,len(pl)))
    
20.     print("共耗时{}秒".format(tt))#0.7s

复制代码

这个是比较慢的版本，100w耗时0.10s

1. from time import time
   
2. 
   
3. def sieve(n):
   
4.     prime = [True] * (n + 1)
   
5.     p = 2
   
6.     while (p * p <= n):
   
7.         if (prime[p] == True):
   
8.             for i in range(p * p, n+1, p):
   
9.                 prime[i] = False
   
10.         p += 1
    
11.     for p in range(2, n):
    
12.         if prime[p]:
    
13.             pl.append(p)
    
14. 
    
15. if __name__=='__main__':
    
16.     pl=[]
    
17.     n = 1000000
    
18.     t1 = time()
    
19.     sieve(n)
    
20.     t2 = time()
    
21.     tt = t2 - t1
    
22.     print(n)
    
23.     print("{}以内素数共{}个:".format(n,len(pl)))
    
24.     print("共耗时",tt,"秒")#0.10s

复制代码

对算法理解比较深的朋友可以来探讨一下为什么两种相同的算法性能会有差别，怎么优化

EvErFrEe

第一种i的步长为2（只计算奇数），第二种p的步长为1；第一种j的步长为2i，第二种i的步长为p。因此第一种更为高效。

EvErFrEe

from time import time

def sieve(n):
    prime = [True] * (n + 1)
    p = 3
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, 2 * p):
                prime[i] = False
        p += 2
    for p in range(3, n， 2):
        if prime[p]:
            pl.append(p)

if __name__=='__main__':
    pl=[2]
    n = 1000000
    t1 = time()
    sieve(n)
    t2 = time()
    tt = t2 - t1
    print(n)
    print("{}以内素数共{}个:".format(n,len(pl)))
    print("共耗时",tt,"秒")#0.10s


这样改更快一点