筛法 · Pacyu

这里介绍几种快速求素数的算法。

Sieve of Eratosthenes (埃氏筛)
#

时间复杂度：$ O(nlglgn) $

#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
int main(int n, char**v)
{
    bool prime[N];
    for(int i = 2; i < N; i++)
        prime[i] = true;
    for (int i = 2; i <= sqrt(N); i++)
        if (prime[i])
            for (int j = i*i; j < N; j += i)
                prime[j] = false;
    for (int i = 2; i < N; i++)
        if (prime[i])
            cout << i << ' ';
    return 0;
}

Sieve of Atkin
#

参见： Sieve of Atkin - wikipedia

Sieve of prime (素数筛)
#

学会这个筛法就可以A掉这个题了：P3383 【模板】线性筛

#include <bits/stdc++.h>
using namespace std;
#define rg register
const int N = 10000010;
int prime[N], notprime[N];
void SievePrime()
{
    int step = 0;
    notprime[1] = 1;
    for (rg int i = 2; i < N; i++)
    {
        if (!notprime[i]) prime[++step] = i;
        for (rg int j = 1; j <= step && prime[j] * i < N; j++)
        {
            notprime[i * prime[j]] = 1;
            if (i%prime[j] == 0) break;
        }
    }
}
int main()
{
    SievePrime();
    for (rg int i = 0; i < N; i++)
        if (prime[i])
            cout << prime[i] << ' ';
    return 0;
}

Sieve of Euler (欧拉筛)
#

原理
#

欧拉函数
#

$ \phi(n) = n \prod_{p|n} (1 - \frac{1}{p}) = \prod(p - 1)p^{k_r - 1} $

其中 $ p $ 为 $ n $ 的所有质因子。它表示在不超过 $ n $ 的正整数中与 $ n $ 互质的数的个数。

如果 $ p $ 是素数，$ k \geq 1 $，那么有

$ \phi(p^k) = p^{k - 1}(p - 1) = p^k(1 - \frac{1}{p}) $

利用这个公式便可以证明欧拉函数。

注意欧拉函数是积性函数，这个性质很重要。

首先 $ n = p_1^{k_1} \cdots p_r^{k_r} $，则

$$ \begin{aligned} \phi(n) &= \phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r}) \\ &= p_1^{k_1}(1 - \frac{1}{p_1})p_2^{k_2}(1 - \frac{1}{p_2}) \cdots p_r^{k_r}(1 - \frac{1}{p_r}) \\ &= p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_r}) \\ &= n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_r}) \end{aligned} $$

与欧拉定理、费马小定理的关系

对任何两个互质的正整数 $ a, m (m >= 2) $，有欧拉定理 $ a^{\phi(m)} = 1(mod \ m) $ (其中 $ \phi(m) $ 是欧拉函数) ，当 $( m $ 是质数 \ p \) 时，式子变为

$ x^{p - 1} = 1(mod \ p) $

即费马小定理。

更多关于欧拉函数，另请参见：

求欧拉函数的算法
#

#include <bits/stdc++.h>
using namespace std;
int eular(int n)
{
    int ret=1;
    for(int i = 2; i*i <= n; i++)
    {
        if(n%i == 0)
        {
            n /= i,ret *= i - 1;
            while(n%i == 0) n /= i, ret *= i;
        }
    }
    if(n > 1) ret *= n - 1;
    return ret;
}
int main()
{
    int n, s;
    cin >> n;
    s = eular(n);
    cout << s << endl;
    return 0;
}

欧拉筛法实现
#

#include <bits/stdc++.h>
using namespace std;
#define rg register
const int N = 10000010;
int prime[N], notprime[N], phi[N];
void SieveEuler()
{
    int step = 0;
    phi[1] = 1;
    for (rg int i = 2; i < N; i++)
    {
        if (!notprime[i]) prime[++step] = i, phi[i] = i - 1;
        for (rg int j = 1; j <= step && prime[j] * i < N; j++)
        {
            notprime[i * prime[j]] = 1;
            if (i%prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i]*(prime[j] - 1);
        }
    }
}
int main()
{
    SieveEuler();
    for (rg int i = 0; i < N; i++)
        if (prime[i])
            cout << prime[i] << ' ';
    return 0;
}

Sieve of Mobius (莫比乌斯筛)
#

原理
#

莫比乌斯函数
#

$ \mu(n) = \eta_{\omega(n)}^{\Omega(n)}\lambda(n) $

这里 $ \lambda(n) $ 是刘维尔函数。

莫比乌斯函数的定义：

For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.

μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.

μ(n) = 0 if n has a squared prime factor.

莫比乌斯函数完整定义的通俗表达：

莫比乌斯函数 $ \mu(n) $ 的定义域是 $ N $;

$ \mu(1) = 1 $;

当$ n $存在平方素因子时，$ \mu(n) = 0 $;

当$ n $是素数或奇数个不同素因子之积时，$ \mu(n) = -1 $;

当$ n $是偶数个不同素因子之积时，$ \mu(n) = 1 $.

即

$$ \mu(n) = \left( \begin{aligned} & 1 \quad n = 1; \\ & (-1)^k \quad n 是无平方因数且 n = p_1 p_2 \cdots p_k \\ & 0 \quad n 有大于 1 的平方因数. \end{aligned} \right. $$

莫比乌斯函数也是一个积性函数（$ \mu(ab) = \mu(a)\mu(b) $，$ a $ 和 $ b $ 互质）

当 $ n = 1 $ 时，$ n $ 的所有因子的莫比乌斯函数值和为 $ 1 $;
当 $ n \neq 1 $ 时，$ n $ 的所有因子的莫比乌斯函数值和为 $ 0 $.

即

$$ \sum_{d|n}\mu(d) = \left( \begin{aligned} 1 \quad n = 1; \\ 0 \quad n > 1. \end{aligned} \right. $$

参考：

莫比乌斯筛法实现
#

#include <bits/stdc++.h>
using namespace std;
#define rg register
const int N = 1000010;
int prime[N], notprime[N], mobius[N];
void SieveMobius()
{
    int step = 0;
    mobius[1] = 1;
    for (rg int i = 2; i < N; i++)
    {
        if (!notprime[i]) prime[++step] = i, mobius[i] = -1;
        for (rg int j = 1; j <= step && prime[j] * i < N; j++)
        {
            notprime[i * prime[j]] = 1;
            if (i%prime[j] == 0)
            {
                mobius[i * prime[j]] = 0;
                break;
            }
            else mobius[i * prime[j]] = -mobius[i];
        }
    }
}
int main()
{
    SieveMobius();
    for (int i = 0; i < N; i++)
        if (prime[i])
            cout << prime[i] << ' ';
    return 0;
}