素数与筛法

定义

如果大于 \(1\) 的正整数 \(p\) 仅有正因子 \(1\) 和 \(p\) 则称 \(p\) 为素数,不是素数且大于 \(1\) 的整数为合数, \(1\) 既不是素数也不是合数

定理

  • 算术基本定理

    任何一个大于 \(1\) 的正整数 \(a\) 都能唯一分解为有限个质数的乘积,写作:

    \[a=p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n} \]

    其中 \(c_i\) 都是正整数, \(p_i\) 都是素数

  • 质数分布定理

    对正实数 \(x\) ,定义 \(\pi(x)\) 为不大于 \(x\) 的素数个数,有 \(\pi(x)\approx\frac{x}{\ln x}\)

判定

如果一个正整数 \(a\) 为合数,则它必定存在一个因子 \(d\) ,且 \(2\leq d\leq \sqrt{a}\)

所以只要对 \(2\sim \sqrt{a}\) 之间的所有整数逐一判断是否是 \(a\) 的因子即可,时间复杂度为 \(O(n)\)

bool is_prime(int a)
{
    if(a < 2)
        return false;
   	for(int i = 2; i * i <= a; i++)
        if(a % i == 0)
            return false;
    return true;
}

筛法

当我们想要知道 \(2\sim n\) 有哪些数是素数,哪些数是合数时,一个自然的想法是对所有数进行一次素数判定,但这种做法时间复杂度为 \(O(n\sqrt{n})\) ,显然不是理想的复杂度

埃氏筛

用一个数组 bool is_prime[i] 表示 \(i\) 是否为一个素数,先假设所有数都是素数,从小到大枚举每一个素数 \(i\) ,把 \(i\) 的倍数(除了本身)都标记为合数。如何枚举质数 \(i\) 呢?当从小到大遍历到一个数 \(i\) 时,若它尚未被标记,则它不能被 \(2\) 到 \(i-1\) 的任何数整除,说明该数为素数

另外,可以发现 \(2\) 和 \(3\) 都会把 \(6\) 标记为合数,因为小于 \(i^2\) 的 \(i\) 的倍数在遍历更小的数时已经被标记过了。所以对于每个 \(i\) ,把大于等于 \(i^2\) 的倍数标记为合数即可,时间复杂度为 \(O(n\log\log n)\)

const int MAX_N = 100000 + 5;
bool is_prime[MAX_N];

void sieve(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    for(int i = 2; i <= n; i++) {
        if(!is_prime[i])
            continue;
        for(int j = i; j * i <= n; j++)
            is_prime[i * j] = false;
    }
}
线性筛

虽然埃氏筛已经达到了较优的复杂度,但仍有优化空间。我们发现,埃氏筛法即使在优化后仍存在重复标记合数的问题,比如 \(12=2\times 6=3\times 4\) ,被标记了两次,其根本原因是埃氏筛不能唯一确定一个合数被标记的方式

所以我们设法让每个合数只被其最小素因子标记,用一个数组 int prime[i] 表示第 \(i\) 个素数的值, 用 bool is_prime[i] 表示 \(i\) 是否为素数,用 int cnt 表示当前筛选出了多少素数,以下算法时间复杂度为 \(O(n)\)

const int MAX_N = 100000 + 5;
bool is_prime[MAX_N];
int prime[MAX_N];
int cnt;

void sieve(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i])
            prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = false;
            if(i % prime[j] == 0)
                break;
        }
    }
}

其中 break 是为了保证 一个合数只会被它最小的素因子筛去 ,我们可以做简单证明:

若 \(i\bmod prime[j] = 0\) ,即 \(prime[j]\mid i,i=k\times prime[j]\)

则 \(\forall t>j, i\times prime[t]=prime[j]\times(k\times prime[t])\)

显然我们可以找到 \(i\times prime[t]\) 的更小素因子 \(prime[j]\) ,所以不应由 \(prime[t]\) 将其筛去

题目

1.NOIP2012 质因数分解

遍历 \(2\) 到 \(\sqrt{n}\) 寻找 \(n\) 的较小因子 \(a\) ,较大因子即为 \(\frac{n}{a}\)

2.CF776B Sherlock

当 \(n\leq 2\) 时,只需要染一种颜色,因为 \(2\) 不是 \(3\) 的素因子

当 \(n\geq 3\) 时,只需要染两种颜色,我们把所有素数都染成颜色 \(1\) ,所有合数都染成颜色 \(2\) ,即满足题意,用线性筛筛出 \(2\) 到 \(n + 1\) 的所有素数即可

3.BZOJ1607 轻拍牛头

对于 \(A_i\) ,如果 \(A_j\mid A_i,i\neq j\) ,那 \(A_i\) 就要拍 \(A_j\)

用数组 int cnt[i] 表示 \(i\) 在序列中出现的次数, int ans[i] 表示序列值为 \(i\) 的牛要拍的次数,对于每个 \(A_i\) ,枚举它的倍数 \(i\times j\) ,如果 \(i\times j\) 在序列中出现,那么序列值为 \(i\times j\) 的牛一定会拍所有序列值为 \(i\) 的牛,所以 ans[i * j] += cnt[i]

#include<bits/stdc++.h>
using namespace std;

int n, maxx = 0, minn = 1e9;
int a[100000 + 5];
int cnt[1000000 + 5], ans[1000000 + 5];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        minn = min(minn, a[i]);
        maxx = max(maxx, a[i]);
        cnt[a[i]]++;
    }
    
    for(int i = minn; i <= maxx; i++)
        if(cnt[i])
            for(int j = 1; i * j <= maxx; j++)
                if(cnt[i * j])
                    ans[i * j] += cnt[i];

    for(int i = 1; i <= n; i++)
        cout << ans[a[i]] - 1 << endl;
    return 0;
}
4.BZOJ2721 樱花

考虑将题目中的式子变形,通分得:

\[\frac{xy}{x+y}=n! \]

移项得:

\[xy-(x+y)n!=0 \]

观察出式子此时变为了类似十字相乘得形式,两边同时加上 \(n!\) 得:

\[(x-n!)(y-n!)=(n!)^2 \]

所以 \(x-n!\) 是 \((n!)^2\) 的约数,确定了 \(x\) 即可确定 \(y\) ,那么问题就转化为了求 \((n!)^2\) 的约数个数

如果 \(n!=p_1^{c1}p_2^{c2}\cdots p_i^{c_i}\) ,则 \((n!)^2=p_1^{2c1}p_2^{2c2}\cdots p_i^{2c_i}\) ,答案为:

\[\prod_{j=1}^i (2c_j+1) \]

对于 \(c_j\) ,有如下公式:

\[c_j=\sum_{l=1}^{\infty}\lfloor\frac{n}{p_j^l}\rfloor \]

可以给出证明:

对 \(2\sim n\) 全部使用唯一分解定理进行分解, \(c_j\) 即为这 \(n-1\) 个分解式中 \(p_j\) 的指数和

设其中 \(p_j\) 的指数为 \(r\) 的分解式有 \(m_r\) 个,可得:

\[\begin{aligned} c_j&=m_1+2m_2+3m_3+\cdots\\ &=(m_1+m_2+m_3+\cdots)+(m_2+m_3+m_4+\cdots)+\cdots\\ &=\lfloor\frac{n}{p_j}\rfloor+\lfloor\frac{n}{p_j^2}\rfloor+\lfloor\frac{n}{p_j^3}\rfloor+\cdots\\ &=\sum_{l=1}^{\infty}\lfloor\frac{n}{p_j^l}\rfloor \end{aligned} \]

所以用线性筛筛出 \(2\sim n\) 的所有素数,代入上述公式即可得到答案

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1000000000 + 7;
const int MAX_N = 1000000 + 5;
int n, cnt;
long long ans = 1;
bool is_prime[MAX_N];
int prime[MAX_N];

void sieve(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i])
            prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = false;
            if(i % prime[j] == 0)
                break;
        }
    }
}

int main()
{
    cin >> n;
    if(n == 1) {
        cout << 0 << endl;
        return 0;
    }
    sieve(n);
    for(int i = 1; i <= cnt; i++) {
        int t = 0;
        for(long long j = prime[i]; j <= n; j *= prime[i])
            t = t + n / j;
        ans = (2 * t + 1) * ans % MOD;
    }
    cout << ans << endl;
    return 0;
}
上一篇:【题解】AT3954 [AGC023C] Painting Machines


下一篇:数学归纳法