筛法最直接的应用就是用于构造素数表,下面先通过构造素数表的问题来讲解常见的两种筛法
普通欧拉筛
原理
构造素数表的筛法是通过已知的素数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