Python:4种质数算法效率比较

import time
#Python：4种质数算法效率比较
def isPrime(n):
    for i in range(2,n):
        if n%i==0:
            return 0
    return 1

def isPrime2(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return 0
    return 1

def isPrime3(n,pn_list):
    num=len(pn_list)
    max=int(n**0.5)+1
    i=0
    k=pn_list[i]
    while i<num and k<max:
        if n % k == 0:
            return 0
        i+=1
        k = pn_list[i]
    return 1

#埃氏筛选法
def isPrime4(pn_list):
    # 将2,3,4,7...质数的倍数位设置为0，表示不是质数
    i = 2
    num = len(pn_list)
    while i < num:
        if pn_list[i] == 1:  # 当前位为质数
            j = 2
            while i * j < num:
                pn_list[i * j] = 0  # 质数的2，3，4，5...倍数都不是质数，将其设置为0
                j += 1
        i += 1


m=100000+1

starttime = time.time()
pn_list = [1]*m
isPrime4(pn_list)

i=2
n=0
x=[]
while i<len(pn_list):
    if pn_list[i]==1:
        n+=1
    i+=1
endtime = time.time()
print(f"isPrime4：{n}个质数，运行时间：{float(endtime-starttime)}秒")

starttime = time.time()
n=1
pn_list=[2]
for i in range(3,m):
    if isPrime3(i,pn_list)==1:
        n+=1
        pn_list.append(i)
endtime = time.time()
print(f"isPrime3：{n}个质数，运行时间：{float(endtime-starttime)}秒")

starttime = time.time()
n=0
for i in range(2,m):
    n=n + isPrime2(i)
endtime = time.time()
print(f"isPrime2：{n}个质数，运行时间：{float(endtime-starttime)}秒")

starttime = time.time()
n = 0
for i in range(2, m):
    n = n + isPrime(i)
endtime = time.time()
print(f"isPrime：{n}个质数，运行时间：{float(endtime - starttime)}秒")

isPrime4：9592个质数，运行时间：0.07588052749633789秒

isPrime3：9592个质数，运行时间：0.13455486297607422秒

isPrime2：9592个质数，运行时间：0.16959810256958008秒

isPrime：9592个质数，运行时间：23.272809743881226秒