五、循环：素数、数位与数论

这一页 3 章 21 道题，开始接触真正的算法。

前面三章的循环是「按部就班地数」——数到 n、加一遍、找最大的。这一页的三个主题不一样：

• 素数：怎么用最少的次数判断？（第一次接触「优化」）
• 数位：怎么把一个数拆得干干净净？
• 因数：两个数之间有什么关系？

这一页出现的三个套路——试除法、拆位数、辗转相除——是后面所有数论题的基础。它们本身不难，但实现的细节充满坑，比如 1 算不算素数、循环到 sqrt(n) 还是 sqrt(n)+1、i*i 会不会溢出。

15. 素数：从暴力到优化

15.1 什么是素数，怎么判断

素数（质数）：只能被 1 和它本身整除的、大于 1 的整数。

注意两个点：必须大于 1（所以 0 和 1 都不是素数），只能被 1 和自身整除。

最直白的判断方法：从 2 试到 n-1，看看有没有能整除的。

bool isPrime(int n) {
    if (n < 2) return false;        // 0 和 1 不是素数
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;   // 找到一个因数，不是素数
    }
    return true;
}

这段逻辑是：只要找到一个能整除 n 的数（除了 1 和 n），n 就不是素数。

s < n 那个循环条件是关键。如果写成 i <= n，那么 n % n == 0 永远成立，所有数都会被判成非素数。

15.2 优化：试到根号就够了

上面的写法能过，但如果题目要判断 1 到 100 万的素数，每个数都试到 n-1，总共要试 10^12 次——肯定超时。

关键观察：如果 n 有一个大于 √n 的因数，那必然还有一个小于 √n 的因数。

比如 36 = 4 × 9，4 小于 6（√36），9 大于 6。你在试到 4 的时候就已经发现它不是素数了，根本不用试到 9。

所以只需要试到 √n：

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {     // 注意：i*i <= n
        if (n % i == 0) return false;
    }
    return true;
}

为什么写 i * i <= n 而不是 i <= sqrt(n)？

• sqrt(n) 返回 double，有精度误差，可能差 1
• 每次循环都调用一次 sqrt，慢
• i * i 是纯整数运算，准又快

代价是：如果 i 很大，i * i 可能溢出 int。所以 n 超过 21 亿时要写成 i <= n / i。

这一行小小的优化，把复杂度从 O(n) 降到 O(√n)。这是你第一次真正体会到「算法比代码重要」——同样的功能，一个 1 秒跑完，一个跑到天荒地老。

15.3 批量判断：一次算一堆

「输出 n 以内的所有素数」——如果每个数都单独判断一遍，总复杂度是 O(n√n)，n = 100 万时大约 10 亿次，很悬。

有两种常用做法：

做法一：边判断边输出（简单，够用）

for (int i = 2; i <= n; i++) {
    if (isPrime(i)) printf("%d ", i);
}

做法二：埃氏筛（更快，值得学）

思路是：找到 2 是素数，把 4、6、8…… 全部标记成「不是素数」；找到 3 是素数，把 6、9、12…… 标记掉；以此类推。

bool isP[1000005];
for (int i = 2; i <= n; i++) isP[i] = true;
for (int i = 2; i <= n; i++) {
    if (!isP[i]) continue;
    for (int j = i * 2; j <= n; j += i) {
        isP[j] = false;         // i 的倍数都不是素数
    }
}

筛法的复杂度接近 O(n log log n)，比逐个判断快得多。这一轮不强制掌握，但你应该能看懂它在干什么——它用的是「如果 x 是素数，那么 x 的倍数都不是」。

15.4 相邻的素数

16. 数位：把数拆开、拼回、再判断

第 4 章用过 /10 和 %10，但那时的位数是固定的。这一章处理位数不固定的数。

16.1 while 拆数位

int n = 12345;
while (n > 0) {
    int d = n % 10;      // 取出最后一位
    printf("%d ", d);    // 5 4 3 2 1
    n = n / 10;          // 砍掉最后一位
}

这个 while 会从右往左走完每一位，不需要知道有几位。这是数位题的标准模板，背下来。

如果要一位一位存起来（比如后面要逆序输出），就边拆边存：

int a[20], cnt = 0;
while (n > 0) {
    a[cnt++] = n % 10;
    n /= 10;
}
// 现在 a[0] 是个位，a[cnt-1] 是最高位，cnt 是位数

注意：这样存下来是逆序的（a[0] 是个位）。要正序输出就倒着遍历。

int n; scanf("%d", &n);
int t = n;              // 留着原来的 n
while (n > 0) { ... n /= 10; }
// 这里 n 已经变成 0 了

16.2 回文数

回文：正着读和倒着读一样。 121、12321 都是。

判断方法有两种：

方法一：把数反转，和原数比

int t = n, rev = 0;
while (t > 0) {
    rev = rev * 10 + t % 10;
    t /= 10;
}
if (rev == n) printf("yes\n");

方法二：转成字符串比较（第 31 章学）

现在用方法一。核心是 rev = rev * 10 + t % 10——第 4 章讲过的「拼接」技巧。

16.3 数位变换的链条

「数字滑滑梯」这类题，规则通常是：把各位数字按某种方式处理后得到一个新数，反复做，直到出现重复或达到某个状态。

int n; scanf("%d", &n);
while (true) {
    // 计算下一个数
    int nxt = ...;
    if (nxt == n) break;        // 或者达到终止条件
    n = nxt;
}

这类题的难点不在循环，在「下一个数怎么算」这个规则本身，通常要用到拆位 + 排序或拆位 + 平方和。

17. 数论基础：因数与倍数

17.1 最大公约数：辗转相除

求两个数的最大公约数（GCD），不要用「从大到小试」——太慢。用欧几里得算法（辗转相除）：

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

它的道理是：gcd(a, b) = gcd(b, a % b)。反复用这个等式，直到余数为 0，此时的除数就是答案。

举个例子，gcd(48, 18)：

答案是 6。

最小公倍数（LCM） 用公式算：

lcm(a, b) = a × b / gcd(a, b)

int lcm = a / gcd(a, b) * b;    // 先除后乘，防溢出

注意顺序：先除后乘。a * b 可能溢出 int，先除以 gcd 再乘就安全得多。

17.2 枚举约数

「n 有多少个约数」「约数之和是多少」——直接试 1 到 n：

int cnt = 0;
for (int i = 1; i <= n; i++) {
    if (n % i == 0) cnt++;
}

同样可以用 √n 优化：约数是成对出现的（i 和 n/i），试到 √n 时一对一对地数：

int cnt = 0;
for (int i = 1; i <= n / i; i++) {
    if (n % i == 0) {
        cnt++;                  // i 是一个约数
        if (i != n / i) cnt++;  // n/i 是另一个（i == n/i 时是平方根，只能算一次）
    }
}

i != n / i 这个判断是防止完全平方数把平方根算两次。比如 36，i = 6 时 n/i 也是 6，只能算一个约数。

17.3 应用：分东西与化简

17.4 区间统计

延伸阅读

服务器上有一整套 OI-Wiki（621 页），是给竞赛选手写的参考手册。下面几页跟这一页相关，但不是每一页都该现在看——标了「现在跳过」的，等以后再说。

• 学完这一页再看：最大公约数 —— 辗转相除法的证明。学会了可以写出比枚举快得多的版本
• 学完这一页再看：素数 —— 前半讲怎么判素数，跟这章一致；后半的 Miller-Rabin、筛法是竞赛内容，跳过
• 现在跳过：数论基础 —— 整除、同余这些形式化定义。数学课会讲，现在看是浪费时间
• 现在跳过：筛法 —— 一次求出几百万以内的所有素数。这章不需要，但你可以先知道有这东西