sieve算法的时间复杂度

Question

与传统的埃拉托斯坦筛不同：

n=10000000
sieve = [True] * n
for i in range(3,int(n**0.5)+1,2):
    if sieve[i]:
        sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
sieve=[2] + [i for i in range(3,n,2) if sieve[i]]

以下增强版本的时间复杂度是多少

n=10000000
sieve5m6 = [True] * (n//6+1)
sieve1m6 = [True] * (n//6+1)
for i in range(1,int((n**0.5+1)/6)+1):
    if sieve5m6[i]:
        sieve5m6[6*i*i::6*i-1]=[False]*((n//6-6*i*i)//(6*i-1)+1)
        sieve1m6[6*i*i-2*i::6*i-1]=[False]*((n//6-6*i*i+2*i)//(6*i-1)+1)
    if sieve1m6[i]:
        sieve5m6[6*i*i::6*i+1]=[False]*((n//6-6*i*i)//(6*i+1)+1)
        sieve1m6[6*i*i+2*i::6*i+1]=[False]*((n//6-6*i*i-2*i)//(6*i+1)+1)
sieve=[2,3] 
for i in range(1,int(n/6)+1):
    if sieve5m6[i]:
        sieve.append(6*i-1)
    if sieve1m6[i]:
        sieve.append(6*i+1)

具有numpy数组函数的更好版本，适用于n>；10^9：

def sieve(n):
    baseW=30
    baseP=np.array([-23,-19,-17,-13,-11,-7,-1,1])
    C=np.ones((len(baseP),len(baseP)), dtype=int)
    C1=np.zeros((len(baseP),len(baseP)), dtype=int)
    C=np.multiply(np.dot(np.diag(baseP),C),np.dot(C,np.diag(baseP)))
    C=C%baseW
    C[C>1] = C[C>1] -baseW
    for i in range(len(baseP))    :
        C1[i,:]=baseP[np.argwhere(C==baseP[i])[:,1]]
    primeB=np.ones((len(baseP),n//baseW+1), dtype=bool)
    for j in range(1,int((n**0.5-baseP[0])/baseW)+1):
        for i in range(len(baseP)):
            if primeB[i,j]:
                for i1 in range(len(baseP)):
                    j1=1-1*i1//(len(baseP)-1)+baseW*j*j+(baseP[i]+C1[i1,i])*j+np.dot(baseP[i],C1[i1,i])//baseW
                    primeB[i1,j1::(baseW*j+baseP[i])] =False
    return np.append([2,3,5],baseP[np.nonzero(primeB.T)[1][len(baseP):]]+baseW*np.nonzero(primeB.T)[0][len(baseP):])

Answer 1

复杂性是一样的。第二个版本可能执行得更快，因为它跳过了更多的因子，但与n的关系在同一数量级

换句话说，你有O（f2）=K*O（f1）=O（f1），其中K是一个常数，与n无关

如果您想要比Eratosthenes筛具有（稍微）更好的时间复杂度的东西，您可能需要查看the sieve of Atkin，尽管由于每次迭代的成本较高，它可能没有更好的总体性能