筛法最直接的应用就是用于构造素数表，下面先通过构造素数表的问题来讲解常见的两种筛法
普通欧拉筛
原理
构造素数表的筛法是通过已知的素数p，来推知p的所有倍数都不是素数，另一方面任何合数都是某个小于它的素数的倍数。所以设2是所有已知的素数，从2开始筛掉所有已知素数的倍数，之后的第一个数必然是素数，将这个数加入已知的素数中，从这个数开始继续筛掉它的倍数，循环此过程就可以得到1~n的素数表。
复杂度分析
对于每个素数\(p\)，需要访问\(\frac{p}{n}\)个合数，所以总时间复杂度为
$$\sum_{i=1\\i:prime}^{i=n}\frac{n}{p} $$
根据
$$\sum_{i:prime\\i=1}^{n}\frac{1}{p}\approx lnlnn $$
知时间复杂度为
$$O(nlnlnn)$$
实现
int n;
vector<char> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i] && (long long)i * i <= n) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
该实现有很多可优化的地方，例如可以直接跳过除2以外的全体偶数。
线性筛
原理
线性筛的关键在于大于2的每个整数的最小素因子是唯一的，如果某个数 \(k\) 是合数，设它的最小素因子为\(lp[k]\)，那么我们只需要在遇到素数\(lp[k]\)时筛掉\( k \)，此后遇到别的素数时不对\( k \)执行“筛”操作，这样就省去了一些重复操作。从素数的那一面来看，每遇到一个素数\( p \)，我们就可以确认除这个数本身以外“以该素数\( p \)为最小素因子的数”都是合数。那么我们还需要知道哪些数的最小素因子是\( p \)，要做到这一点，我们需要维护一个数组\( lp \)，\( lp[i] \) 表示\(i\)的最小素因子，如果\(i\)是素数，那么\( lp[i]==i\) 。每遇到一个素数\(prime[j]\)，所有满足\(lp[i]\ge prime[j]\)的\(i*prime[j]\)的最小素因子就是\(prime[j]\)。这样从小到大进行维护，就成功构造了素数表。
复杂度分析
原理处已经解释过，每个合数只会被访问一次，所以线性筛法的复杂度是\(O(n)\)
实现
const int MAXN = (int) 1e6 + 5;
int lp[MAXN]; vector<int> prime;
inline void sieve() {
fill(lp, lp + MAXN, 0);
for (int i = 2; i < MAXN; ++i) {
if (lp[i] == 0) {
lp[i] = i;
prime.push_back(i);
}
for (int j = 0; j < prime.size() && (long long) i * prime[j] < MAXN && lp[i] >= prime[j]; ++j) {
lp[i * prime[j]] = prime[j];
}
}
}
此处也可以维护一个bool型的数组is_prime来标识某个数是否为素数，用条件i%prime[j]==0来判断跳出。
筛法与积性函数
几乎所有的积性数论函数都可以用线性筛来计算，下面是一般的规则（假定函数为f）
- 如果i是素数，根据定义直接给出函数值\( f(i) \)
- 考虑i与某个素数p，如果i与p互素，则\(f(ip)=f(i)f(p)\)
- 如果i包含因子\(p\)，则需要利用别的关系来确定其值。不过一般而言这个关系是简单的，例如对于欧拉函数\(\varphi\)，如果\(i\%p==0\)，那么\(\varphi(ip)=\varphi(i)p\)
这里给出利用线性筛计算欧拉函数的一个例子
const int MAXN = (int) 1e6 + 5;
bool is_composite[MAXN];
vector<int> prime;
int phi[MAXN];
inline void sieve() {
fill(is_composite, is_composite + MAXN, false);
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!is_composite[i]) {
phi[i] = i - 1;
prime.push_back(i);
}
for (int j = 0; j < prime.size() && (long long) i * prime[j] < MAXN; ++j) {
is_composite[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
题目
SPOJ LCMSUM
SPOJ GCDEX
SPOJ NAJPWG
Uva 11327
(题解会有的，总之我先摸着)
参考
https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
Comments | NOTHING