猫史档案馆

一 阅读须知

此作品为python3.12制作。时间等数据为个人电脑测得，略有差异，敬请谅解。

二 前言

在做一系列关于素数筛的题目中，若用埃氏筛，python经常超时（比c++慢10倍）。虽然欧拉筛能够过，但其理解起来有些复杂，不过，今天以及以后的一系列优化，将使埃氏筛的效率超越欧拉筛。

三  埃氏筛初步

题目要求：输入一个数（2<=n<=10000000）输出n以内所有的素数

import time
d=int(input())
t1=time.time()
c=[False]*(d+1)
for i in range(2,d+1):
    if not c[i]:
    print(i,end=' ')
    for j in range(1,d//i+1):
        c[i*j]=True
t2=time.time()
print(t2-t1)

以上即最基础的埃氏筛。

当测试数据达到最大值时，所用时间为4.74秒，大大超出了时间。接下来，我们要对此进行优化。（下一篇再开始）