https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
枚举每个质数，筛到质数的倍数
for (int i = 2; i <= n; i++) { if (v[i] == 0) { for (int j = i; j <= n; j += i) { // if (v[j] == 0) 有的人只有在v[j]是0还没有被筛的情况下，做下面的事情 v[j] = i; // j 的质因数是 i // 如果不加 if 同一个数字会被筛多次，v[j] 记录的是 j 的最大的质因数 // 如果加 if 同一个数字也会被筛多次（如果想值筛一次，用欧拉筛法） v[j] 是 j 的最小的质因数 } } } // 如果 v[i] == i 意味着 i 是质数
这个写法一个数组记录最小的质因数（或者说是最大的质因数）
如果需要压缩空间，也可以用 01数组 (bitset) 记录是否是质数
时间复杂度 可以保证每个数只被筛一次
和上一个方法相比，需要一个数组记录到目前为止生成了哪些质数
void init() { // vis[i] 表示 i 最小的质因数 for (int i = 2; i < MAXN; ++i) { if (!vis[i]) { // i 没有被筛掉，i是质数 pri[cnt++] = i; // 把i加入质数数组 vis[i] = i; } for (int j = 0; j < cnt && i * pri[j] <= n; ++j) { // 无论i是不是质数，i都和已有的所有质数尝试一下，把尝试的结果标记成合数 vis[i * pri[j]] = pri[j]; // 标记 i * pri[j] 的质因数是 pri[j] // 同一个位置可能被标记多次（12 = 4 * 3 = 6 * 2） // 目标让每个数字只被标记一次 // 要求 pri[j] 必须是 i*pri[j] 的最小质因数 if (vis[i] == pri[j]) // 也可以写作 i % pri[j] == 0 之这么写是为了避免除法，加速运算 { break; // 如果 i 包含 质因数 pri[j] // 之后比如对于 i*pri[j+1] 这个数字 pri[j+1] 不是最小质因数 } } } }
可以用筛法求出 1到n中的质数 和 每个数字的最小质因数
如果知道 每个数字的最小质因数，那么可以很快的分解质因数
筛法预处理积性函数的值
phi[1] = 1 // 欧拉函数 mu[1] = 1 // 莫比乌斯函数 dcnt[1] = 1 // 约数个数 dsum[1] = 1 // 约数和 for (int i = 2; i <= n; i++) { if (v[i] == v[i / v[i]]) // 如果 i 和 i/v[i] 最小质因数相等，意味着 i 中 v[i] 的次数大于1 { phi[i] = phi[i / v[i]] * v[i]; mu[i] = 0; dcnt[i] = 2 * dcnt[i / v[i]] - dcnt[i / v[i] / v[i]]; dsum[i] = dsum[i / v[i]] * v[i] + (dsum[i / v[i]] - dsum[i / v[i] / v[i]] * v[i]); } else { phi[i] = phi[i / v[i]] * (v[i] - 1); mu[i] = -mu[i / v[i]]; dcnt[i] = dcnt[i / v[i]] * 2; dsum[i] = dsum[i / v[i]] * (1 + v[i]); } }
https://www.luogu.com.cn/problem/P3383
有一个做法可以直接求 1 到 n 个质数个数
注意到 R-L <= 1e6
注意到 2 ** 31 以下的合数，一定有一个 <=sqrt(R) 的质因数
用一个长度为 R-L+1 的数组存每个数字是否是合数
f[i] 表示 i 是否是合数
如果 f[i] == 1 表示 L+i 是合数
如果 f[i] == 0 表示 L+i 是质数
枚举所有 <= sqrt(R) 的质数 p
枚举在L到R之间的，所有 p 的倍数（不包括 p 本身）设为i
标记i是合数
#include <bits/stdc++.h> using namespace std; long long l, r; int v[1000020]; // v[i] 表示 i 的最大质因数是多少 // 最后一次被谁筛掉，比如 30 会被 2 3 5 筛掉 3 次，最后 v[30]=5 int f[1000020]; // f[i] 表示 l+i 是不是合数，如果 f[i]==1 说明 l+i 被某个质数筛掉过，是合数 void gao(int p) { // 枚举 p 的所有倍数 // 但是不枚举1倍，p本身是质数！至少2倍 for (long long i = max((l + p - 1) / p, 2LL) * p; i <= r; i += p) { f[i - l] = 1; } } int main() { scanf("%lld%lld", &l, &r); // 计算出 <= sqrt(r) 所有质数 for (int i = 2; i <= r / i; i++) { // 如果i没有被标记过，说明i是质数 if (!v[i]) { // 发现质数 i // 去筛掉 L到R 之间的所有合数 gao(i); } for (int j = i; j <= r / j; j += i) { // 标记i的倍数 v[j] = i; } } int z = 0; for (int i = 0; i <= r - l; i++) { // f[i] 表示 l+i 是不是合数 // 如果 f[i]==0 说明 l+i 是质数 if (!f[i]) { z++; } } printf("%d\n", z); return 0; }
欧拉函数
phi(x) 从1到x有多少个数字和x互质
n = a1 ** b1 * a2 ** b2 * ... * ak ** bk
phi(n) = n * (1 - 1/a1) * (1 - 1/a2) * .. * (1 - 1/ak)
360 = 2**3 * 3**2 * 5**1
phi(360) = 360 * (1-1/2) * (1-1/3) * (1-1/5) = 96
1到x有多少个数字与x不互质 x-phi(x)
#include <bits/stdc++.h> using namespace std; const int mod = 666623333; long long a[1000020]; // a[i] 初始是 l+i 如果发现了质因数，就从中约掉，最后剩下什么 long long f[1000020]; // f[i] = phi(i + l) long long l, r; int v[1000020]; void gao(int p) { for (long long i = (l + p - 1) / p * p; i <= r; i += p) { while (a[i - l] % p == 0) // 无论质因数 p 出现多少次，都约掉 { a[i - l] /= p; } f[i - l] = f[i - l] / p * (p - 1); // 无论质因数 p 出现多少次，只做一次 / p * (p - 1) } } long long phi(long long x) { int re = x; for (long long i = 2; i * i <= x; i++) { if (x % i == 0) { re = re / i * (i - 1); while (x % i == 0) { x /= i; } } } if (x > 1) { re = re / x * (x - 1); } return re; } int main() { scanf("%lld%lld", &l, &r); for (int i = 0; i <= r - l; i++) { a[i] = l + i; f[i] = l + i; } for (int i = 2; i <= r / i; i++) { if (!v[i]) { gao(i); } for (int j = i; j <= r / j; j += i) { v[j] = i; } } long long z = (l + r) % mod * (r - l + 1) % mod * 333311667 % mod; // l + l+1 + ... + r-1 + r for (int i = 0; i <= r - l; i++) { if (a[i] > 1) // 约掉所有 <= sqrt(r) 的质数之后，如果剩下的数字不是1，那么一定是质数 { f[i] = f[i] / a[i] * (a[i] - 1); // 修改 f[i] } z = (z - f[i]) % mod; } printf("%lld\n", (z + mod) % mod); return 0; }
https://www.spoj.com/problems/FACTCG2/
https://www.spoj.com/problems/SITB/