prime=[] st=[Falsefor i in range(0,n+1)] st[0]=True st[1]=True
# 朴素筛法-O(nlogn) defget_prime(N): for i in range(2,N+1): if st[i]==False: prime.append(i) for j in range(i+i,N+1,i):#不管是合数还是质数,都用来筛掉后面它的倍数 st[j]=True
#诶氏筛法 O(nloglogn) defget_prime(N): for i in range(2,N+1): if st[i]==False: prime.append(i) for j in range(i+i,N+1,i):#可以用质数就把所有的合数都筛掉 st[j]=True
#线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍 #算法核心:x仅会被其最小质因子筛去 defget_prime(N): for i in range(2,N+1): if st[i]==False: prime.append(i) for it in prime:#对于任意一个合数x,假设pj为x最小质因子,当i<x/pj时,一定会被筛掉 if it*i>N:break st[it*i]=True if i%it==0: break #1.i%pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子 #2.i%pj != 0, pj定小于 i的所有质因子,所以pj也为pj*i最小质因子