为什么筛的时候退出条件不能这样写

Devpp @ 2024-07-02 01:37:10

int n, q;   cin >> n >> q;
vector<int> pri;
bool is_pri[n+1];
memset(is_pri, 1, sizeof(is_pri));
for(int i=2; i<=n; i++){
  if(is_pri[i])   pri.push_back(i);
  for(int &x: pri){
    if(x*i > n || i%x == 0) break;
      is_pri[x*i] = false;
    }
}

by PengAo @ 2024-07-02 07:30:08

其实应该这样写：若大于 n 就退出 \rightarrow 将 is_pri[x*i] 置为 false \rightarrow 若 i%x==0 则退出。

by fzj2007 @ 2024-07-02 07:39:58

@Devpp 这样筛不到最小质因子的次数不为 1 的数

by zhangbo1000 @ 2024-07-02 07:41:38

@Devpp i\bmod x=0 说明 x 是 i 的因数，而根据筛的顺序，所有 x 单调递增，因此满足 i\bmod x=0 的 x 是 i 的最小的质因数。

线性筛的原理是使每个数只被它的最小质因数筛掉，而既然确定了 x 是 i 的最小质因数，那么对于所有 y>x，i\times y 的最小质因数为 x 而不是 y，所以要 break，但 i\times x 的最小质因数明显还是 x，所以要筛掉，实现上就是筛掉后再判断。