笔记汇总

代码

void init(int n)
{
    // 质数从 2 开始出现
    for (int i = 2; i <= n; i ++ )
    {
        if (!v[i]) p[ ++ m] = i;    // 没有被更小的质因子标记过，所以为质数
        for (int j = 1; p[j] * i <= n; j ++ )   // 通过质因子标记合数，不能大于上界 n
        {
            v[i * p[j]] = true;         // 标记为合数
            if (i % p[j] == 0) break;   
            // 此时 p[j] 为 i 的一个质因子，也就是存在一个 t，满足 p[j] * t == i
            // 因为要求每个合数仅被它的最小素因子筛去正好一次，i 的质因数若小于 p[j]，
            // 就不满足为最小质因数，所以直接退出
        }
    }
}

优化

因为一个数 $n$ 的最小质因数不超过 $\sqrt{n}$，

所以我们只需要预处理 $0$ 到 $\sqrt{n}$ 范围内的质数，

就可以在 $O((r-l)logn)$ 的时间内找出 $l$ 到 $r$ 之间的所有质数（$l <= r <= n$）

阶乘分解

因为 $N!$ 中的质因数，等于 $[1, n]$ 中每个数的质因数的总和，

对于某质因数 $p$，其倍数都包含这个质因数，则共有 $[\frac{n}{p}]$ 个，

由此可知 有两个质因子 $p$ 的数，个数为 $[\frac{n}{p^2}]$，用线性筛筛出质数后，累计即可。

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

const int N = 1e6 + 10;

int n, m;
int p[N], v[N];

inline bool check(int a, int b)
{
    return a / b * b == a;
}

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!v[i]) p[ ++ m] = i;
        for (int j = 1; p[j] * i <= n; j ++ )
        {
            v[p[j] * i] = 1;
            if (check(i, p[j])) break;
        }
    }
}

int main()
{
    scanf("%d", &n);
    init(n);

    for (int i = 1; i <= m; i ++ )
    {
        int s = 0;
        for (int j = n; j; j /= p[i]) s += j / p[i];
        printf("%d %d\n", p[i], s);
    }

    return 0;
}