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

fjqz177

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

from time import time

def ess(n):
    pl = [2]
    Td = [True] * (n + 1)
    for i in range(3, n + 1, 2):
        if Td[i]:
            pl.append(i)
            for j in range(i ** 2, n + 1, i * 2):
                Td[j] = 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 = [True] * (n + 1)
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    for p in range(2, n):
        if prime[p]:
            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

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

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


这样改更快一点