随列表规模增长的计时操作异常：质数生成耗时骤降问题

我想知道用Python生成1到N的质数列表需要多长时间，并绘制耗时随N变化的曲线图。我用SymPy的sieve.primerange实现了代码，但预期耗时应该随N单调递增，实际却出现了耗时骤降的情况。

代码如下：

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer
from sympy import sieve

T = []
tic=timer()

N= np.logspace(1,8,30)
for Nup in N:
    tic = timer()
    A=list(sieve.primerange(1,Nup))
    toc = timer()
    T.append(toc-tic)
    
plt.loglog(N,T,'x-')
plt.grid()
plt.show()

生成的耗时曲线图存在明显的骤降异常。

核心原因：SymPy Sieve的全局缓存机制 #

SymPy的sieve是一个全局筛法对象，它会永久缓存已经计算出的所有质数。调用sieve.primerange(1, Nup)时：

• 如果Nup小于等于当前缓存的质数上限，会直接从缓存提取结果，几乎不消耗时间；
• 只有当Nup超过缓存上限时，才会运行筛法扩展到目标上限，此时耗时才会显著增加。

代码中骤降现象的具体触发场景 #

你的代码用np.logspace(1,8,30)生成对数间距的N值，整体虽递增，但两种情况会导致耗时骤降：

1. 浮点Nup的整数重复：logspace生成的是浮点数，部分相邻Nup的整数上限可能相同（比如100.2和100.8的整数部分都是100），第二次调用时直接读取缓存，耗时骤降；
2. 小范围缓存扩展：当某个Nup仅比之前的缓存上限大一点时，筛法只需扩展极小范围，耗时远小于首次筛到较大上限的时间，在log-log图上就会表现为骤降。

验证与修正方法 #

要验证缓存的影响，可以在每次循环前清空sieve的缓存，强制每次重新计算：

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer
from sympy import sieve

T = []
N= np.logspace(1,8,30)
for Nup in N:
    sieve._reset()  # 清空缓存，强制重新计算质数
    tic = timer()
    A=list(sieve.primerange(1,Nup))
    toc = timer()
    T.append(toc-tic)
    
plt.loglog(N,T,'x-')
plt.grid()
plt.show()

修改后，耗时会随N呈现近似单调递增的趋势，符合质数生成的时间复杂度规律。

补充：质数生成的时间复杂度 #

生成N以内的质数，埃氏筛的时间复杂度为O(n log log n)，因此耗时本应随N单调递增，缓存机制是导致你看到异常骤降的唯一原因。

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