title: ACM-学习记录-素数筛tags: ACM
abbrlink: 91338f8a
date: 2020-11-20 20:09:57

前言

近期发现我NEFU低年级组校赛题目只有模拟+数论，恰恰都是我最不会做的，数论方面反反复复用到的就是素数筛，特在此记录一下，闲来无事自己翻阅当作复习复习，以免被到时候一道题都做不出来菜到巨佬们。

代码

查找2-N的所有素数，如下

  1. //线性筛
  2. void init() {
  3.   phi[1] = 1;
  4.   for (int i = 2; i < MAXN; ++i) {
  5.     if (!vis[i]) {
  6.       phi[i] = i - 1;
  7.       pri[cnt++] = i;
  8.     }
  9.     for (int j = 0; j < cnt; ++j) {
  10.       if (1ll * i * pri[j] >= MAXN) break;
  11.       vis[i * pri[j]] = 1;
  12.       if (i % pri[j]) {
  13.         phi[i * pri[j]] = phi[i] * (pri[j] - 1);
  14.       } else {
  15.         // i % pri[j] == 0
  16.         // 换言之，i 之前被 pri[j] 筛过了
  17.         // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
  18.         // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
  19.         // 掉就好了
  20.         phi[i * pri[j]] = phi[i] * pri[j];
  21.         break;
  22.       }
  23.     }
  24.   }
  25. }

数论确实是想杀了我- -