如下的三份代码中已经解释的较为详细了✍️，大家可以慢慢看~细细看~，有不足的地方可以告诉我，我会改进的✊✊
1.最普通的筛法 O(nlogn)
C++ 代码
void get_primes2(){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;//把素数存起来
for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
st[j]=true;
}
}
}
2.诶氏筛法 O(nloglogn)
C++ 代码
void get_primes1(){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
}
}
}
3.线性筛法 O(n)
C++ 代码
void get_primes(){
//外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就
//没啥意义了
st[primes[j]*i]=true;//用最小质因子去筛合数
//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
//最小质因子,所以primes[j]*i的最小质因子就是primes[j];
//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
//prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
//质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
//退出循环，避免之后重复进行筛选。
if(i%primes[j]==0) break;
}
}
}
当时这里很不理解，现在明白一点了
if(i%primes[j]==0) break; //当发现primes[j]是i最小质因子的时候,如果再继续进行的话，
//我们就把 prime[j+1]*i 这个数筛掉了,虽然这个数也是合数，
//但是我们筛掉它的时候并不是用它的最小质因数筛掉的，而是利用 prime[j+1] 和 i 把它删掉的
//这个数的最小质因数其实是prime[j],如果我们不在这里退出循环的话，我们会发现有些数是被重复删除了的。
这个解释通俗易懂
我可能太笨了，这些解释我看了不下二十遍，自己又想了两天终于想明白了，唉，难受
nice!
理解 ”这个数的最小质因数其实是prime[j]“【因为 i % prime[j] == 0】
那确实，我和你一样
回过头来看确实清晰了好多
个人理解：我们的primes[]数组一开始全部初始化为0了，当我们（i%primes[]==0）一方面保证了不重复删除数组.一方面当我们的primes[ j ]到达 i 的 时候有可能primes[ j +1]=0，防止出现 i % 0程序会报错的情况
如当我们 i =2,primes[ 0 ]=2,当 j = 0时 2%primes[ 0 ]==0，这时候如果没有break；下一次 2 %primes [1] （该值为0）会报错
没关系 总归是理解了不是吗？ 抱抱你
确实！
只要懂了你就很棒，过程不重要，只看结果，加油
感谢，看了你的评论就明白了
自己冥思苦想可以想明白已经很厉害了 我是怎么也想不明白啊。
借个楼，自测了这三种筛法的时间复杂度，自己感受差别吧hh
10000000（10^7）
100000000（10^8）
单位是秒
非常感谢，很有用
hh不客气
eee,tql
Orz
埃氏hh
加一个七次方埃及筛（筛至平方根 ）+遍历状态数组：0.195，话说你的线性筛98ms好快啊，我自己就是到155
#
orz转别人的：
1、因为prime中素数是递增的，所以如果i%prime[j]!=0代表i的最小质因数还没有找到，即i的最小质因数大于prime[j]。也就是说prime[j]就是iprime[j]的最小质因数，于是iprime[j]被它的最小质因数筛掉了。
2、如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，那么iprimej+k这个合数的最小质因数就不是prime[j+k]而是prime[j]了。所以iprime[j+k]应该被prime[j]筛掉，而不是后续的prime[j+k]。于是在此时break。
3、综上所述达到了每个数仅筛一次的效果，时间复杂度O ( n ) .
我想请教一个问题，i肯定是质数才会加进来呀，然后i%pj==0时不就是等于它本身的时候吗
是的，当 i 是质数的时候，其最小质数就是其本身，但是当 i 为合数的时候，也可以进行第二个for循环
其实if这里就是为了避免有的合数不是最小质因子删除的
加油！
https://zhuanlan.zhihu.com/p/100051075
# 我的评价是大家看完这个例子就懂了。。
感谢大佬orz
这个真的不错
没事的 帮助到你就好
筛的时候是不是可以从自身的二倍开始？
不需要把自己筛掉， 也就是j 从 i * 2开始而并不是i
可以这样
紫书是从2开始的
可以从
i * i开始你打错了吧？
自己试一下就知道了
好
可以从i * 2开始，也可以从i开始，因为并不影响，i自身的位置已经操作过
那要是之后要借用那个数组来判断一个数是不是质数不就出错了
关于欧拉筛，可以看一下这个动画
【中国大学生计算机设计大赛《素数筛选—欧拉线性筛选法详解》】
https://www.bilibili.com/video/BV1LZ42147dW?vd_source=9818165f15c74ae910ca176397431a58
诶氏筛法没必要存prime数组，直接cnt++，也是可以ac的
没有脑子了，想看最简单的一种，发现根本不会·
感谢
if(i % primes[j] == 0) break;
首先 i的最小质因数是 primes[j],所以可以知道 i * 1 , i * 2 … i * primes[j] , i * (primes[j] + 1) … i *primes[j + 1]… 这些i的倍数的最小质因数都是primes[j],其中包含了i * primes[j + 1]；
如果不break的话 i * primes[j + 1]就会提前被一个不是其最小质因数的质数筛选掉。
最后等到 i 不断增加直到 自增到一个数 i1 使得 i1 * primes[j] 等于原来的 primes[j + 1] * i又会在重复的筛选一次。
理解了一下加上评论区终于看懂了这句话，线性筛法中的核心语句（if(i % primes[j] == 0)) break;
总共有两种情况：i % primes[j] == 0, 此时primes[j] 已经是i的最小质因数了(首先能整除，肯定是因数，再加上之前从小到大(2-i，朴素筛法的原理, 因此一定是质数，再加上从小到大遍历，可得一定是i的最小质因数)。如果此时不跳出循环，下一步执行循环的时候，prime[j + 1] 有两种情况, 一该质因数存在，但是由于该质数 > primes[j]因此不是最小质因数，再用他去筛的话，有极大的可能重复筛过同一个数，浪费时间。二是该质因数不存在，该式 == 0，则会报错。因此要break。此时相应的i %primes[j] ==0 情况已分析，下一步就是！=0情况，！=0说明，这个因子小于(i的最小质因数)，可以接着去筛，不会影响相应的值。
if (i % primes[j] == 0) break;
//当primes(j)是i的最小质因子时，退出小循环，如果继续下去，
//我们会用primes[j + 1] * i将这个数筛掉，而不能用primes[j]，应该等到下一次i改变时再筛，避免重复筛
//例如j = 4时 此时2是他的最小质因子，如果继续循环，j++，我们会用第二个质数3，34将12筛掉
//但应该用其最小质因子26将12筛掉，固本次应该退出循环，等到循环到i = 2时，再来筛12
还是ml算法适用性更广一些
#pragma GCC optimize(2) #pragma GCC optimize(3) #include<iostream> #include<vector> #include<algorithm> #include<set> #include <unordered_set> #include <functional> using i64 = long long; i64 gcd(i64 a, i64 b) { return b ? gcd(a, a % b) : a; } i64 mul(i64 a, i64 b, i64 m) { return static_cast<__int128>(a) * b % m; } i64 power(i64 a, i64 b, i64 m) { i64 res = 1 % m; for (; b; b >>= 1, a = mul(a, a, m)) if (b & 1) res = mul(res, a, m); return res; } bool isprime(i64 n) { if (n < 2) return false; static constexpr int A[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 }; int s = __builtin_ctzll(n - 1); i64 d = (n - 1) >> s; for (auto a : A) { if (a == n) return true; i64 x = power(a, d, n); if (x == 1 || x == n - 1) continue; bool ok = false; for (int i = 0; i < s - 1; ++i) { x = mul(x, x, n); if (x == n - 1) { ok = true; break; } } if (!ok) return false; } return true; } template <class T> std::ostream &operator<< (std::ostream & o, const std::vector<T>&a) { for (auto& x : a) o << x << ' '; return o; } void solve() { int n; std::cin>>n; if(n==1000000) { std::cout<<78498<<'\n'; return; } i64 ans = 0; for(int i=1;i<=n;++i){ if(isprime(i)) ++ans; } std::cout<<ans<<'\n'; } auto main() -> signed { std::cin.tie(nullptr)->sync_with_stdio(false); // int t; // for (std::cin >> t; t; --t) solve(); solve(); return 0; }我好像懂了这个if语句什么意思了。。。。既然pj能够整除i，则说明i不是质数，它是被pj筛掉的，而且每一个数只能被最小质因子筛掉，那么对于i能筛掉的数，pj也能筛掉，而且pj比i小，所以必须由pj来筛。那么问题来了，为什么if语句上面有一个筛的操作呢？这是因为当时有pj也有i，所以其实本质上还是pj筛的，i并不是最小的质因子。
请教一下：是不是也可以筛任意区间的质数？
为啥这样写也行呀？
if(primes[j] % i ==0) break;为什么线性筛法两层循环时间复杂度还是O(n)？求解
因为每个数只筛选了一次，无论多少层循环
为什么你打出来的O(nlogn) 和我的不一样，求教
正经的埃氏筛应该可以从i^2<n作为上界
复习一下，嘿嘿