关于埃拉托斯特尼筛法时间复杂度及两类增强优化版时间复杂度的技术问询

咱们先从你给出的那个只处理奇数的基础优化筛说起——它的时间复杂度还是O(n log log n)，只是常数因子比传统埃氏筛小了一半，毕竟跳过了所有偶数，少处理了一半的数。

接下来咱们看看你提到的两类增强优化版的时间复杂度：

第一类：基于6k±1规则的增强版筛法 #

这个版本利用了一个关键的数学规律：除了2和3之外，所有质数都可以表示成6k±1的形式。通过这个规则，它把需要标记的范围进一步缩小，只处理符合这个形式的数。

不过从渐近时间复杂度的角度来说，它依然是O(n log log n)。原因很简单：它的核心逻辑还是埃氏筛的本质——用找到的质数去标记其所有倍数，只是通过数学规则减少了需要处理的元素数量，大幅降低了常数因子（大概只需要处理原来1/3左右的数，排除了2、3的倍数），但主导时间增长的log log n项并没有改变。

对应的代码如下：

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） #

这个版本玩得更极致，用了30作为基数（30是2、3、5的最小公倍数），把质数的范围缩小到30k±1、30k±7、30k±11、30k±13、30k±17、30k±19、30k±23这些形式，同时借助numpy的向量化操作来提升批量处理的效率，特别适合n超过1e9的超大场景。

但不管怎么优化，它的渐近时间复杂度依然是O(n log log n)。numpy的向量化操作只是让常数因子变得更小，尤其是在处理超大数据时，内存利用和批量操作的优势会非常明显，但核心逻辑还是埃氏筛的变体——用质数标记其倍数，所以主导时间增长的项没有变化。另外这个版本的空间效率很高，因为它只存储符合特定形式的数的标记，对于n>1e9的场景，空间占用比普通筛法小很多。

对应的代码如下：

import numpy as np

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):])

内容的提问来源于stack exchange，提问作者user140242