当时这里很不理解，现在明白一点了

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）

• 最普通的筛法：1.606
• 埃及筛：0,316
• 线性筛：0.098

100000000（10^8）

• 最普通的筛法：28.134
• 埃及筛：3.756
• 线性筛：0.948

单位是秒

非常感谢，很有用

hh不客气

eee,tql

$\color{#661111}{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自身的位置已经操作过

那要是之后要借用那个数组来判断一个数是不是质数不就出错了

没有脑子了，想看最简单的一种，发现根本不会·

感谢

理解了一下加上评论区终于看懂了这句话，线性筛法中的核心语句（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

诶氏筛法没必要存prime数组，直接cnt++，也是可以ac的

还是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作为上界

复习一下，嘿嘿

关于欧拉筛，可以看一下这个动画
【中国大学生计算机设计大赛《素数筛选—欧拉线性筛选法详解》】
https://www.bilibili.com/video/BV1LZ42147dW?vd_source=9818165f15c74ae910ca176397431a58

这里为什么没有初始化cnt