线性筛及其应用

发布于 2019-03-09  4,541 次阅读


筛法最直接的应用就是用于构造素数表,下面先通过构造素数表的问题来讲解常见的两种筛法

普通欧拉筛

原理

构造素数表的筛法是通过已知的素数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)

  1. 如果i是素数,根据定义直接给出函数值​\( f(i) \)
  2. 考虑i与某个素数p,如果i与p互素,则\(​f(ip)=f(i)f(p)\)
  3. 如果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

https://cp-algorithms.com/algebra/prime-sieve-linear.html

https://codeforces.com/blog/entry/54090


终有一日, 仰望星空