筛算法的时间复杂度

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 无关。

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

筛算法的时间复杂度

Time complexity of sieve algorithm

python

primes

sieve

time-complexity

sieve-of-eratosthenes