36 · 质数与整除：筛法与分解

正整数只有两类：除 1 和自身外没有别的因子的叫质数，有的叫合数。这个划分之所以重要，是因为唯一分解定理：任何大于 1 的整数都能写成若干质数之积，写法唯一。所以数论题的第一步几乎总是“把这个数拆成质数”，而拆之前必须先知道哪些数是质数。

先证明第一条结论，它决定了后面所有循环的边界。若 n = a·b 且 a ≤ b，则 a·a ≤ a·b = n，所以 a ≤ √n。也就是说：n 只要有真因子，就一定有一个不超过 √n。于是“试完 2..√n 都没有因子”与“n 是质数”完全等价。n = 10^12 时这是 10^6 次除法对 10^12 次除法——六个数量级的差距，就在这一个不等号上。

这一节的两个基础工具都很短，但每一行都有理由。先把结构看清楚，之后所有代码都是它们的变体。

bool isPrime(long long n) {
    if (n < 2) return false;                       // 0、1 不是质数
    if (n % 2 == 0) return n == 2;                // 唯一的偶质数是 2
    for (long long i = 3; i <= n / i; i += 2) {   // 只试奇数，且防止 i*i 溢出
        if (n % i == 0) return false;
    }
    return true;
}

int n;  cin >> n;
vector<char> isp(n + 1, 1);              // 先假设 2..n 全是质数
isp[0] = isp[1] = 0;                     // 0、1 不是质数
for (int i = 2; i <= n / i; ++i) {       // 优化一：外层只到 √n
    if (!isp[i]) continue;               // i 是合数，它的倍数早被更小的质数划过了
    for (int j = i * i; j <= n; j += i)  // 优化二：从 i*i 起
        isp[j] = 0;
}
// 此时 isp[k] == 1 的 k 就是质数

筛表：
  isp[0] = isp[1] = 0;  其余 0..L 全置 1
  i 从 2 到 L/i：若 isp[i]，把 i*i, i*i+i, i*i+2i, ... 标 0

装口袋：
  sum = 0, cnt = 0
  i 从 2 到 L：
      若 isp[i] 为 0，跳过
      若 sum + i > L，break
      否则 sum += i, cnt += 1

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

const int MAXN = 100005;         // L ≤ 10^5，多留几个位置
bool isp[MAXN];                  // isp[i] = true 表示 i 是质数

int main() {
    int L;
    cin >> L;

    // ---------- ① 埃氏筛：标出 2..L 的所有质数 ----------
    fill(isp, isp + L + 1, true);        // 只填 0..L，别填满 MAXN
    isp[0] = isp[1] = false;             // 0 和 1 不是质数，漏了答案会多算一个

    for (int i = 2; i <= L / i; ++i) {   // 外层只到 √L：更大的 i 划不动任何新数
        if (!isp[i]) continue;           // i 自己是合数，跳过
        for (int j = i * i; j <= L; j += i) {
            isp[j] = false;              // 从 i*i 起划，2i..(i-1)i 已被更小的质数划掉
        }
    }

    // ---------- ② 从小到大装 ----------
    int cnt = 0, sum = 0;
    for (int i = 2; i <= L; ++i) {
        if (!isp[i]) continue;           // 不是质数
        if (sum + i > L) break;          // 再加就超重；后面的质数更大，一定也超
        sum += i;
        ++cnt;
    }

    cout << cnt << "\n" << sum << "\n";
    return 0;
}

埃氏筛有个小浪费：一个合数会被它的每个质因子各划一次，比如 30 会被 2、3、5 各划一遍。线性筛把它修掉——让每个合数只被它的最小质因子划一次，代价是多用一个数组 primes 存已找到的质数，顺手还能免费得到每个数的最小质因子表 lpf。

const int MAXN = 1000000 + 5;
vector<int> primes;          // 已找到的质数，从小到大
int lpf[MAXN];               // lpf[k]：k 的最小质因子
bool isp[MAXN];              // 是否是质数

void eulerSieve(int n) {
    primes.clear();                          // 多测：上一轮攒下的质数必须清掉
    fill(isp, isp + n + 1, true);
    isp[0] = isp[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (isp[i]) {
            primes.push_back(i);
            lpf[i] = i;                        // 质数的最小质因子是它自己
        }
        for (int p : primes) {
            if ((long long)p * i > n) break;   // 越界，后面的 p 只会更大
            isp[p * i] = false;
            lpf[p * i] = p;                    // p 是 p*i 的最小质因子
            if (i % p == 0) break;             // ★ 关键的一句，见下表
        }
    }
}

分解质因数就是试除法的直接应用，只有一个新要点：除干净之后，剩下的那部分不用再试。因为每除一次 n 就变小，循环条件 p ≤ n/p 会自动收紧；而循环结束时若 n 仍大于 1，这个 n 一定是质数（否则它会有个不超过 √n 的因子，早就被除走了）。

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

int main() {
    long long n;
    cin >> n;
    cout << n << " = ";

    bool first = true;
    for (long long p = 2; p <= n / p; ++p) {   // 上界跟着 n 一起缩小
        if (n % p != 0) continue;              // p 不是因子
        int c = 0;
        while (n % p == 0) { n /= p; ++c; }    // 除干净，c 就是指数
        if (!first) cout << " * ";
        cout << p << "^" << c;
        first = false;
    }
    if (n > 1) {                               // 剩下的一定是质数
        if (!first) cout << " * ";
        cout << n << "^1";
    }
    cout << "\n";
    return 0;
}

最后一招：R 可以很大（10¹²），但区间长度 R−L 很小（10⁶）。筛法筛不了 10¹² 个位置，可我们只需要 [L, R] 这一小段。做法是：先筛出 √R ≤ 10⁶ 以内的质数，再用这些质数去划 [L, R] 里的倍数，下标整体平移 L，用一个长度 R−L+1 的数组装下。

// 统计 [L, R] 内的质数个数，要求 L ≥ 1，R ≤ 10^12，R - L ≤ 10^6
long long countPrimes(long long L, long long R) {
    int lim = (int)sqrt((long double)R) + 1;        // 只需 √R 以内的质数
    vector<char> small(lim + 1, 1);
    small[0] = small[1] = 0;
    for (int i = 2; i <= lim / i; ++i)
        if (small[i])
            for (int j = i * i; j <= lim; j += i) small[j] = 0;

    vector<char> seg(R - L + 1, 1);                 // seg[k] 对应数字 L + k
    if (L == 1) seg[0] = 0;                         // 1 不是质数

    for (int i = 2; i <= lim; ++i) {
        if (!small[i]) continue;
        long long p = i;
        // 从 p*p 与 “不小于 L 的最小 p 的倍数” 中取较大者
        long long start = max(p * p, (L + p - 1) / p * p);
        for (long long j = start; j <= R; j += p) seg[j - L] = 0;
    }

    long long cnt = 0;
    for (long long k = L; k <= R; ++k) cnt += seg[k - L];
    return cnt;
}

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

int main() {
    long long n;
    cin >> n;

    // n = p * q 且 p < q 都为质数，则 p < √n，从 2 往上找第一个因子即是 p
    for (long long i = 2; i <= n / i; ++i) {
        if (n % i == 0) {              // 第一个因子就是较小的质数 p
            cout << n / i << "\n";     // 较大的是 q = n / p
            return 0;                  // 找到即结束，不必再试
        }
    }
    return 0;
}