Lesson 07: 求素数 CNB

练习任务

编写一个 C 程序，找出 1~100 范围内的最大素数。素数（质数）是指大于 1 的正整数，且只能被 1 和自身整除——例如 2、3、5、7、11、13、... 你需要从 1 到 100 遍历每个候选数，使用试除法判断每个数是否为素数，记录遇到的最大素数。

期望输出：

max prime is 97

提示：判断素数只需试除到 sqrt(n)——想想为什么不需要试除到 n-1？你需要 math.h 中的 sqrt 函数（注意编译时加 -lm），并处理好浮点数到整数的类型转换。试除法中发现约数后应立即 break 退出内层——因为已经确定该数不是素数。

核心知识点

• 素数定义与数学性质 — 大于 1 的自然数，仅被 1 和自身整除，2 是唯一偶素数
• 素数历史与欧几里得证明 — 素数有无穷多个，反证法的经典应用
• 试除法朴素算法 — 从 2 到 n-1 逐一尝试能否整除，时间复杂度 O(n)
• sqrt 优化 — 试除到 sqrt(n) 即足够，复杂度降至 O(√n)
• 数学头文件 math.h — sqrt、pow、sin、cos、fabs、ceil、floor 等数学函数
• 与数学库的链接 -lm — <math.h> 中的函数定义在 libm，需显式链接
• 浮点数到整数的转换 — double → int 的隐式转换与显式 (int) 强制类型转换
• (int) 截断语义 — 向零截断（truncation toward zero），与 floor/trunc 的对比
• 三层逻辑嵌套 — 外层遍历候选数 → 中间计算 sqrt 上界 → 内层试除
• break 提前退出 — 发现约数后立即跳出内层，减少无意义的后续试除
• 循环终值判断素数 — j == tmp + 1 的含义：内层完整走完说明未找到约数
• 标志变量替代 — int is_prime = 1 写法，意图更明确，代码自解释
• sqrt 上界的数学原理 — 若 n 有约数 d > sqrt(n)，则 n/d < sqrt(n) 必为约数
• 跳过偶数优化 — 除 2 外所有偶数都不是素数，跳过可减半试除次数
• 仅试除素除数 — 合数约数必然能被更小的素约数整除，只试除素数即可
• 埃拉托斯特尼筛法 — O(n log log n) 批量找出 N 以内全部素数
• 素数定理 — π(n) ≈ n / ln(n)，素数分布的渐近规律
• 模运算与素性测试 — Fermat 小定理、Miller-Rabin 测试的概念介绍
• 实际应用 — 密码学 RSA、哈希函数、伪随机数生成中的素数角色
• 找最大素数 vs 找全部素数 — 两种需求的不同策略
• 纯整数替代 — i * i <= num 避免 math.h 和浮点运算

代码框架

prime_skeleton.c

#include <stdio.h>
#include <math.h>

int main(void)
{
    int num;
    int i;
    int max = 0;

    // 外层循环：遍历 1~100，对每个候选数判断是否为素数
    for (num = 1; num <= 100; num++)
    {
        int bound;

        // 中间计算：bound = (int)sqrt(num)，获得试除上界
        bound = (?????) sqrt(?????);

        // 内层循环：i 从 2 到 bound，逐一试除 num
        for (i = 2; i <= bound; i++)
        {
            if (num % i == 0)
                // 发现约数，num 不是素数 —— 这里应该做什么？
                /* 填空：跳出内层循环 */;
        }

        // 如果 i == bound + 1，说明内层循环完整走完 —— num 是素数
        if (/* 判断条件 */)
            max = num;
    }

    printf("max prime is %d\n", max);

    return 0;
}

填充以上框架的关键思考：sqrt 的参数应该是什么类型？求值结果是什么类型？如何转换为 int？内层循环遇到约数后如何中止？最终如何判断是否完整走完了内层循环？

TIP

先不要往下翻看参考解答。尝试自己填完框架后编译运行（记得 gcc -o prime prime.c -lm）。用几个你已知的素数（如 11、13、13×13=169）验证你的判断逻辑是否正确。同时思考：从 1 开始循环有什么问题？1 是素数吗？

---

深度讲解

1. 素数：定义、历史与试除法

1.1 素数的数学定义

素数（Prime Number）是大于 1 的自然数，且只能被 1 和自身整除。换句话说：大于 1 的整数 n 是素数，当且仅当不存在整数 d（2 ≤ d < n）使得 n % d == 0。

素数    : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
非素数  : 1（太小，现代定义排除）, 4（=2×2）, 6（=2×3）, 8（=2×4）, 9（=3×3）, 10（=2×5）, ...

几个关键特性：

1. 2 是唯一的偶素数——所有大于 2 的偶数都能被 2 整除，因此都不是素数
2. 素数有无穷多个——欧几里得在公元前 300 年左右就给出了优雅的证明
3. 1 不是素数——现代定义明确排除了 1，因为算术基本定理要求素因子分解唯一：如果 1 是素数，则 6 = 2×3 = 1×2×3 = 1×1×2×3，分解不唯一
4. 每个大于 1 的整数都可以唯一分解为素数的乘积——这就是算术基本定理（Fundamental Theorem of Arithmetic），素数是整数的「原子」

1.2 素数的历史与欧几里得的无穷性证明

素数研究的历史可追溯到古希腊时期。欧几里得在《几何原本》（Elements，约公元前 300 年）第九卷命题 20 中给出了素数有无穷多个的经典证明——这是数学史上最早、最优雅的反证法之一：

欧几里得的证明：

假设素数只有有限个，将它们全部列出：p₁, p₂, ..., pₙ。

构造一个新数：N = p₁ × p₂ × ... × pₙ + 1

现在分析 N 的性质：

• 如果 N 是素数：那么我们就找到了一个不在原列表中的素数，与「素数只有这些」矛盾
• 如果 N 是合数：那么 N 必有一个素因子 q。这个 q 不可能是 p₁, p₂, ..., pₙ 中的任何一个——因为 N 除以任意 pᵢ 都余 1。所以 q 是一个不在原列表中的新素数，同样产生矛盾

无论哪种情况都导出矛盾，因此假设不成立——素数必有无穷多个。

这个证明距今已有 2300 多年，至今仍然是数学入门课程中最受推崇的证明之一。它的美妙之处在于：不依赖任何高深定理，只用乘法、加法和反证法三步推理。

1.3 试除法：最直观的判断方法

给定一个数 n，判断它是否为素数的最直接方法就是试除法（Trial Division）——逐一尝试 2 到 n-1 之间的每个整数，看是否能整除 n：

trial_division_naive.c

// 判断 n 是否为素数——朴素试除法
int is_prime(int n)
{
    if (n <= 1)
        return 0;            // 1 和更小的数不是素数

    for (int d = 2; d < n; d++)
    {
        if (n % d == 0)      // d 能整除 n → n 不是素数
            return 0;
    }

    return 1;                // 没有约数 → n 是素数
}

这称为试除法（Trial Division）——尝试所有可能的除数。对于每个候选数 n，需要执行 n-2 次取模运算。100 以内有 25 个素数，朴素试除法对每个数都要完整遍历。

时间复杂度分析：对于单个候选数 n，朴素试除法需要 O(n) 次检查。如果我们要找 1~N 中所有素数，总复杂度为 O(N²)——随着 N 增大，计算量急剧膨胀。

1.4 使用 break 提前退出

一旦发现一个约数，就不需要再试其他约数——n 已经确定不是素数：

trial_division_break.c

for (int d = 2; d < n; d++)
{
    if (n % d == 0)
    {
        found_divisor = 1;
        break;               // 提前退出：已确定不是素数
    }
}

break 在这里的价值：对于合数，它让循环在找到第一个约数时就停止——而不是傻傻地试完所有 n-2 个除数。例如 n=100，第一个约数 d=2 就能让循环停止，只需 1 次检查而非 98 次。

但对于大素数（如 97），朴素试除法仍需试除到最后才知道它是素数——因为根本没有约数可发现。

---

2. 从 O(n) 到 O(√n)：sqrt 优化的数学原理

2.1 为什么只需试除到 sqrt(n)？

这是整个素数判断算法中最关键的洞察。定理：如果 n 是合数，则它至少有一个不超过 sqrt(n) 的非平凡因子。

证明：

设 n = a × b，其中 a 和 b 都是大于 1 的整数，且不妨设 a ≤ b。

由 a ≤ b 得：a × a ≤ a × b = n，即 a² ≤ n，所以 a ≤ sqrt(n)。

这意味着：如果 n 有大于 sqrt(n) 的约数（即 b），那么它必然有一个对应的不超过 sqrt(n) 的约数（即 a）。因此我们只需要在 2 到 floor(sqrt(n)) 范围内寻找约数——如果找不到，n 就是素数。

直观示例: n = 100
  sqrt(100) = 10
  大于 10 的约数: 20, 25, 50
  它们对应的较小约数: 5(=100/20), 4(=100/25), 2(=100/50) —— 全都不超过 10
  所以我们只需在 2~10 范围内试除

另一角度：约数是成对出现的。如果 d 是 n 的约数，则 n/d 也是。这两个约数中，较小的那个必然不超过 sqrt(n)。所以我们只需要找到较小的那个——找不到就说明 n 是素数。

2.2 效率对比

方法	试除范围	n=97 需试除的除数个数	n=997 需试除的除数个数
朴素法	2 ~ n-1	95 次	995 次
sqrt 法	2 ~ sqrt(n)	8 次（2~9）	30 次（2~31）

对于 97 这个素数，sqrt 法将试除次数从 95 降到 8——减少了约 91%。对于更大的数，改进更加显著：

n = 997 (素数):  朴素法 995 次 → sqrt 法 30 次  (减少 97%)
n = 10007 (素数): 朴素法 10005 次 → sqrt 法 99 次 (减少 99%)
n = 100003 (素数): 朴素法 100001 次 → sqrt 法 315 次 (减少 99.7%)

复杂度：朴素试除法对单个候选数 O(n)，sqrt 优化后降为 O(√n)——这是一个从线性到亚线性的巨大飞跃。

---

3. math.h 与 sqrt 函数

3.1 C 数学库概览

<math.h> 是 C 语言的标准数学头文件。它声明了大量数学函数，这些函数的实现位于独立的数学库 libm 中。以下是常用函数分类：

类别	函数	声明	用途
幂与根	sqrt	double sqrt(double x)	平方根
	pow	double pow(double x, double y)	x 的 y 次幂
	cbrt	double cbrt(double x)	立方根（C99）
三角函数	sin	double sin(double x)	正弦（弧度）
	cos	double cos(double x)	余弦（弧度）
	tan	double tan(double x)	正切（弧度）
	atan2	double atan2(double y, double x)	反正切（y/x，带象限）
指数对数	exp	double exp(double x)	e 的 x 次幂
	log	double log(double x)	自然对数 ln(x)
	log10	double log10(double x)	常用对数 log₁₀(x)
取整	ceil	double ceil(double x)	向上取整
	floor	double floor(double x)	向下取整
	trunc	double trunc(double x)	向零截断（C99）
	round	double round(double x)	四舍五入（C99）
绝对值	fabs	double fabs(double x)	浮点数绝对值
余数	fmod	double fmod(double x, double y)	浮点除法余数

共同特征：所有数学函数都接受和返回 double 类型。这是经过深思熟虑的设计——数学结果天然是实数（如 sqrt(2) ≈ 1.41421356...），用 double 能保留最大精度。如果你需要整数结果，需要在调用后自行转换。

3.2 与数学库的链接：-lm 的必要性

仅 #include <math.h> 并不足够——还必须告诉链接器（linker）把数学库包含进来：

gcc -o prime prime.c -lm     # -lm = link with libm
gcc prime.c -lm -o prime     # 也可以放在 .c 前面
gcc -o prime prime.c -lm -Wall   # 推荐：同时开启所有警告

为什么只有 math.h 需要特殊的 -lm？

C 标准库分成两个「包」：

┌─────────────────────────────────────┐
│   libc (默认自动链接)                 │
│   ├── 输入输出: printf, scanf, ...   │
│   ├── 字符串: strlen, strcpy, ...    │
│   ├── 内存: malloc, free, ...        │
│   └── 其他标准功能                    │
├─────────────────────────────────────┤
│   libm (需要手动 -lm)                 │
│   ├── 幂与根: sqrt, pow, cbrt, ...   │
│   ├── 三角: sin, cos, tan, ...       │
│   ├── 指数对数: exp, log, ...        │
│   └── 取整/绝对值: ceil, floor, ...  │
└─────────────────────────────────────┘

历史原因：早期 Unix 系统（1970 年代 PDP-11）磁盘空间极为有限，编译器安装时需要精打细算。数学函数体积较大且不是每个程序都需要，所以被分离到独立的 libm 中——使用时需显式指定。现代系统上磁盘空间已不是问题，但因兼容性保留了这一约定。Linux 上的 glibc 和 macOS 上的 libSystem 都继承了这一传统。

WARNING

如果不加 -lm，你会看到链接错误：undefined reference to 'sqrt'。这不是语法错误——编译器能找到 sqrt 的声明（math.h 里有），但链接器找不到它的定义（libm 没被链接）。编译和链接是两个不同的阶段：#include <math.h> 只满足编译阶段的需求（提供函数原型），-lm 才满足链接阶段的需求（提供函数实现）。

3.3 链接过程的深入理解

C 程序的构建分四个阶段：

源文件 (.c) ──预处理──→ 翻译单元 ──编译──→ 目标文件 (.o) ──链接──→ 可执行文件
                                    ↑                            ↑
                              #include <math.h>               -lm 链接 libm
                              只提供 sqrt 的声明              提供 sqrt 的实现

**声明（declaration）**告诉编译器函数的签名——参数类型、返回类型。**定义（definition）**提供函数的实际实现代码。math.h 中只有声明，实现在 libm.a（静态库）或 libm.so（共享库）中。

NOTE

有些编译器（如较新版本的 gcc）在某些配置下会自动链接 libm。但不应依赖此行为——标准要求显式指定 -lm，可移植代码必须包含它。

3.4 sqrt 函数的细节

double sqrt(double x);

• 参数：一个 double 类型的非负数（传负数理论上返回 NaN，行为由实现定义）
• 返回值：x 的平方根，类型为 double
• 精度：通常精确到最后一位（IEEE 754 要求正确舍入）

在素数判断中，我们传整数给 sqrt：

sqrt(97)    // 隐式转换: int 97 → double 97.0
sqrt(100)   // 隐式转换: int 100 → double 100.0

C 语言在函数调用时会对参数进行默认实参提升（default argument promotion），int 会被自动转换为 double。但为了代码清晰，也可以显式转换：

sqrt((double)num)    // 显式转换，意图更明确

---

4. 强制类型转换 (int) 与浮点→整数转换

4.1 为什么需要转换

sqrt 返回 double，但我们需要一个 int 作为循环上界：

int bound;
bound = (int)sqrt(num);   // 将 double 强制转换为 int

没有显式转换会怎样？

bound = sqrt(num);        // 隐式转换，编译器给 warning

double 隐式赋值给 int 在 C 语言中是允许的（C 会隐式进行类型调整），但编译器会发出警告：warning: implicit conversion from 'double' to 'int' changes value from 9.8488578 to 9——明确告诉你小数部分将被丢弃。

使用显式的 (int) 强制类型转换有三个好处：

1. 明确意图：告诉阅读者「这里有意丢弃小数部分，不是疏忽」
2. 消除编译器警告：告诉编译器「我知道这可能损失精度，这是我想要的行为」
3. 代码审查友好：在大型项目中，显式转换是良好实践——配合 -Werror（警告即错误）时尤其重要

4.2 (int) 的截断语义：向零截断

(int) 转换执行的是向零截断（truncation toward zero）——直接丢弃小数部分，不进行任何舍入：

(int) 3.14   → 3
(int) 3.99   → 3    ← 注意：不是四舍五入！
(int) 4.0    → 4
(int) -3.14  → -3   ← 向零截断（不是向下）
(int) -3.99  → -3   ← 向零截断（不是向下）

与 floor/ceil/trunc 的对比：

函数	x=3.7	x=3.2	x=-3.7	x=-3.2	语义
(int)x	3	3	-3	-3	向零截断（truncation toward zero）
floor(x)	3.0	3.0	-4.0	-4.0	向下取整（向负无穷）
ceil(x)	4.0	4.0	-3.0	-3.0	向上取整（向正无穷）
trunc(x)	3.0	3.0	-3.0	-3.0	向零截断（C99）
round(x)	4.0	3.0	-4.0	-3.0	四舍五入（C99）

对于 sqrt(n)，由于 n ≥ 0 保证了结果非负，(int) 和 floor() 以及 trunc() 行为一致——都等于向下取整。例如：

sqrt(97)  = 9.8488578...  →  (int) → 9
sqrt(100) = 10.0          →  (int) → 10
sqrt(2)   = 1.4142135...  →  (int) → 1

这对素数判断来说是合理的——我们需要试除到 floor(sqrt(n))，即不超过 sqrt(n) 的最大整数。sqrt(n) 本身如果是整数（如 sqrt(25) = 5.0），则它对应的约数就是 sqrt(n)，需要被检测到。

4.3 浮点精度陷阱

WARNING

浮点数运算存在精度误差。理论上 sqrt(25) 应该是精确的 5.0，但由于浮点表示的限制，实际可能返回 4.999999999999999。(int)4.999999999999999 = 4，循环只运行到 i=4，而 5 才是 25 的约数——导致将 25 误判为素数。

对于 100 以内的小整数，sqrt 的精度通常足够安全（IEEE 754 要求 sqrt 正确舍入）。但严谨的写法应该加上安全余量：

bound = (int)(sqrt(num) + 1e-9);   // 加一个小 epsilon 避免截断误差

或者更好的方式——完全避免浮点运算（见下文 7.3 节）。

4.4 C 语言中的类型转换体系

C 语言支持两种类型转换方式：

隐式转换（Implicit Conversion）：编译器自动执行，不需要语法标记：

double d = 3;        // int → double：值保留，精度扩展
int i = 3.14;        // double → int：小数截断，可能警告
int j = 'A';         // char → int：值保留（ASCII 65）

显式转换 / 强制类型转换（Explicit Conversion / Cast）：

int i = (int)3.14;          // C 风格强制转换
double d = (double)97;      // 明确意图
int *p = (int *)malloc(8);  // void* → int* 转换

C 风格强制转换 (type)expression 功能强大但不够安全——它可以在任意指针类型之间转换而不报警告。在 C++ 中引入了更安全的 static_cast、dynamic_cast 等。在 C 语言中，使用强制转换时应确保自己知道在做什么。

---

5. 三层逻辑嵌套

5.1 三层结构剖析

README 中的参考代码看似两层循环，但实际上包含三层逻辑嵌套：

three_layer_nesting.c

for (num = 1; num <= 100; num++)      // 第1层: 遍历每个候选数
{
    int tmp;
    int j;

    tmp = (int)sqrt(num);              // 第2层: 对每个候选数计算试除上界
    for (j = 2; j <= tmp; j++)         // 第3层: 对每个候选数试除
    {
        if (num % j == 0)
            break;
    }
    if (j == tmp + 1)                  // 判断内层循环是否完整走完
        max = num;
}

三层逻辑的职责：

1. 外层（候选数循环 num = 1..100）：遍历范围内的每个数，对每个数重复整个判断流程。这是「做什么」的层面——遍历候选集
2. 中间计算层（sqrt 上界计算 tmp = (int)sqrt(num)）：对每个候选数计算个性化的试除上界。它不是循环结构，而是外层循环体内的一个计算步骤——但它是连接外层和内层的关键桥梁
3. 内层（试除循环 j = 2..tmp）：对每个候选数逐一尝试每个可能的除数。这是「怎么做」的层面——具体判断一个数是否为素数

数据流：外层提供候选数 num → 中间层根据 num 计算上界 tmp → 内层用 tmp 限制试除范围。三层各司其职，数据自上而下流动。

5.2 与 Lesson 06 乘法表的嵌套对比

方面	Lesson 06（乘法表）	Lesson 07（素数判断）
外层循环	按行遍历（i=1~9）	按候选数遍历（num=1~100）
中间计算	无（内层上界直接用外层变量）	计算 sqrt(num) 得到动态上界
内层循环上界	j <= i（下三角动态边界）	j <= sqrt(num)（平方根边界）
内层体操作	printf 打印乘积	num % j == 0 试除判断
break 用法	无 break（按需也可加）	检测到约数立即 break
循环后判断	无（内层结束后直接换行）	j == tmp + 1 判定素数
嵌套性质	两层纯循环嵌套	循环 + 计算 + 循环三层逻辑嵌套

两种结构都用到嵌套循环 + 动态内层上界——但目的不同：一个是生成数据（打印乘法表各项），另一个是验证性质（判断素数）。乘法表的内层上界由外层变量 i 直接决定，而素数判断的内层上界由 sqrt(num) 计算得出——这多了一层「计算」逻辑。

5.3 执行流程追踪

以 num=15（合数）和 num=17（素数）为例，追踪三层逻辑的执行过程：

num = 15（合数，15 = 3×5）：

外层 num=15
  ├── 中间层 tmp = (int)sqrt(15) = (int)3.8729... = 3
  ├── 内层 j=2: 15 % 2 = 1 ≠ 0 → 继续
  ├── 内层 j=3: 15 % 3 = 0 → 发现约数！break
  └── 判断: j(=3) == tmp+1(=4)? → 否，不更新 max

num = 17（素数）：

外层 num=17
  ├── 中间层 tmp = (int)sqrt(17) = (int)4.1231... = 4
  ├── 内层 j=2: 17 % 2 = 1 ≠ 0 → 继续
  ├── 内层 j=3: 17 % 3 = 2 ≠ 0 → 继续
  ├── 内层 j=4: 17 % 4 = 1 ≠ 0 → 继续
  ├── 内层 j=5: 5 <= 4? → 否，循环正常结束
  └── 判断: j(=5) == tmp+1(=5)? → 是！更新 max = 17

---

6. 循环终值判断素数：j == tmp + 1 的含义

6.1 循环退出后的变量值分析

这是本课最有技巧性的编程模式。理解它的关键是追踪 for 循环退出后循环变量的终值：

loop_final_value.c

for (j = 2; j <= tmp; j++)
{
    if (num % j == 0)
        break;           // 发现约数，提前退出
}
// 循环结束后 j 的值有两种可能：
// 情况 A: 因 break 退出 → j 停留在退出时的值 (满足 j ≤ tmp)
// 情况 B: 因条件 j <= tmp 为假而正常结束 → j == tmp + 1

情况 A（发现约数）：break 使循环立即终止，j 不再递增，停留在导致 break 的值。此时 j ≤ tmp——因为内层循环条件是 j <= tmp，j 只有在这个范围内才会执行循环体。

情况 B（未发现约数）：循环正常执行完最后一轮后，j++ 使 j 变为 tmp + 1，此时条件 j <= tmp 为假，循环退出。所以 j 的终值是 tmp + 1。

j == tmp + 1 就是「内层循环完整走完了」的标志——只有没遇到任何 break（即没找到约数）时，才满足此条件。

6.2 为什么不能写成 j == tmp？

for (j = 2; j <= tmp; j++)
    ...
if (j == tmp)     // ❌ 错误：永远无法到达！

在正常结束的情况下（没遇到 break），j 从 2 递增到 tmp，每次循环末尾 j++。当 j 等于 tmp 时，条件 j <= tmp 仍然为真——循环还会执行一轮。执行完后 j++ 变为 tmp + 1，此时条件为假才退出。所以循环结束时 j 不可能等于 tmp——必然是 tmp + 1。

如果你写 if (j == tmp)，这个条件将永远为假：

• break 退出时 j ≤ tmp，但 break 时 j 通常远小于 tmp（找到第一个约数就停了）
• 正常退出时 j = tmp + 1，不等于 tmp

更宽容的写法：if (j > tmp) 也能达到同样效果——正常结束时 j = tmp + 1 > tmp，break 退出时 j ≤ tmp。这个写法不依赖具体的终值，更健壮，也更容易理解。

6.3 用标志变量替代

利用循环终值是一种精巧但可读性较差的技巧。在生产代码中，通常用标志变量（flag variable）替代：

flag_variable.c

int is_prime = 1;              // 假设是素数
for (j = 2; j <= tmp; j++)
{
    if (num % j == 0)
    {
        is_prime = 0;          // 发现约数，不是素数
        break;
    }
}
if (is_prime)                  // 或用 if (is_prime == 1)
    max = num;

两种写法的对比：

方面	循环终值判断 j == tmp + 1	标志变量 is_prime
代码行数	较少（少一行声明）	较多（多一个变量声明和赋值）
可读性	需要理解循环终值语义	意图明确，代码自解释
维护性	如果修改循环条件，判断也要改	变量语义独立于循环细节
出错风险	易写错（如误写成 j == tmp）	不易出错
教学价值	帮助理解 for 循环执行机制	展示良好的编程习惯

建议：学习阶段理解循环终值判断有助于深入掌握 for 循环机制，但实际编程中推荐使用标志变量——意图更明确，代码自解释（self-documenting）。

6.4 for 循环执行机制的完整回顾

结合本课和 Lesson 05、06 的知识，完整理解 for 循环的执行流程：

for (初始化①; 条件②; 递增④)
{
    循环体③
}

执行顺序：① → ② → ③ → ④ → ② → ③ → ④ → ② → ...

• 初始化只在开始时执行一次
• 每次循环前检查条件，为真则进入循环体
• 每次循环体执行完后执行递增
• 条件为假时循环终止，不执行循环体

理解了这一点，就明白了为什么循环正常结束时 j 是 tmp + 1 而不是 tmp——j 先递增到 tmp + 1，然后条件检查失败，循环不执行就退出了。

---

7. 算法优化思路

7.1 跳过偶数

除了 2 以外，所有偶数都能被 2 整除——因此都不是素数。跳过偶数可以将试除次数减半：

skip_evens.c

if (num == 2)
    max = 2;                     // 2 是素数，单独处理
if (num > 2 && num % 2 != 0)     // 只看大于 2 的奇数
{
    for (i = 2; i <= tmp; i++)
    {
        if (num % i == 0)
            break;
    }
    if (i == tmp + 1)
        max = num;
}

更进一步，外层的步长也可以优化为 num += 2（从 3 开始，每次跳 2），直接跳过所有偶数候选：

// 2 单独处理后，从 3 开始只遍历奇数
max = 2;
for (num = 3; num <= 100; num += 2)  // 步长为 2，只检查奇数
{
    // ... 试除判断
}

7.2 只试除素数

一旦我们知道 2 是素数，后续所有能被 2 整除的合数（4、6、8、10...）就都不需要作为除数——因为如果 num 能被 6 整除，它一定能被 2 整除。任何合数除数都能被更小的素除数替代。

因此，试除时可以只使用已发现的素数作为除数：

only_prime_divisors.c

int primes[25];        // 存储已发现的素数
int p_count = 0;

for (num = 2; num <= 100; num++)
{
    int is_prime = 1;
    for (int k = 0; k < p_count && primes[k] * primes[k] <= num; k++)
    {
        if (num % primes[k] == 0)
        {
            is_prime = 0;
            break;
        }
    }
    if (is_prime)
        primes[p_count++] = num;   // 新发现的素数加入列表
}

对于 100 以内的数，只试除素数而非所有数：素除数只有 2, 3, 5, 7（因为 sqrt(100) = 10，10 以内的素数只有这些），而非 2~9 八个除数。

7.3 无 math.h 的纯整数方案

如果不使用 math.h 和 -lm，可以用乘法代替平方根：

方案 A：i * i <= num 作为循环条件

no_math_h_loop_condition.c

for (i = 2; i * i <= num; i++)
{
    if (num % i == 0)
        break;
}
if (i * i > num)        // 等价于 i > sqrt(num)，内层完整走完
    max = num;

i * i <= num 在数学上等价于 i <= sqrt(num)（对正数），且完全避免了浮点运算和类型转换——纯粹整数运算。

方案 B：手动计算 sqrt 上界

manual_sqrt_bound.c

int bound = 0;
while (bound * bound <= num)
    bound++;
bound--;    // 回退到满足 bound² ≤ num 的最大整数

整数溢出的注意事项：

WARNING

i * i <= num 在 num 很大时可能导致整数溢出。例如当 i = 50000 时，i × i = 2,500,000,000，超过了 32 位有符号整数的最大值 2,147,483,647（2³¹ - 1），会发生溢出（undefined behavior）。对于 100 以内的数完全安全。在实际项目中需要根据数据范围选择合适的方案：小范围用 i * i <= num，大范围用 sqrt 或 i <= num / i（避免溢出）。

方案 C：用除法避免乘法溢出

for (i = 2; i <= num / i; i++)   // 等价于 i * i <= num，但不会溢出
{
    if (num % i == 0)
        break;
}

i <= num / i 在数学上等价于 i * i <= num，但除法的中间结果不会超过 num，因此不会溢出。

7.4 从大到小遍历策略

如果目标是找「最大素数」而非「所有素数」，从 100 往 1 方向遍历更高效——找到的第一个素数就是答案，不需要遍历剩余的数：

descending_traversal.c

for (num = 100; num >= 2; num--)
{
    // 跳过大于 2 的偶数
    if (num > 2 && num % 2 == 0)
        continue;

    for (i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
            break;
    }

    if (i * i > num)    // 是素数
    {
        printf("max prime is %d\n", num);
        break;           // 找到第一个就停止！
    }
}

从大到小找最大素数的优势：找到 97 后就停止——只检查了 100、99、98、97 四个数（其中 100、98 因偶数跳过，99 = 9×11 是合数）。而从小到大需要遍历全部 100 个数。

7.5 埃拉托斯特尼筛法（Sieve of Eratosthenes）

如果要找出 N 以内的所有素数（而非仅最大素数），埃拉托斯特尼筛法是效率最高的经典算法。它由古希腊数学家埃拉托斯特尼（Eratosthenes of Cyrene，公元前 276-194 年）发明，距今已有 2200 多年。

算法思想：

1. 列出 2 到 N 的所有整数，假设它们都是素数
2. 从最小的素数 2 开始，将 2 的所有倍数标记为「非素数」
3. 找到下一个未被标记的数（3），它是素数，将其所有倍数标记为「非素数」
4. 重复直到处理到 sqrt(N)
5. 剩下的未被标记的数就是素数

sieve_of_eratosthenes.c

#include <stdio.h>

#define N 100

int main(void)
{
    int sieve[N + 1];          // sieve[i] = 1 表示 i 是素数
    int i, j;

    // 初始化：假设所有 >=2 的数都是素数
    for (i = 2; i <= N; i++)
        sieve[i] = 1;

    // 筛法主循环：对每个素数，筛掉它的倍数
    for (i = 2; i * i <= N; i++)
    {
        if (sieve[i])           // i 是素数
        {
            // 从 i*i 开始标记（更小的倍数已被之前的素数筛过）
            for (j = i * i; j <= N; j += i)
                sieve[j] = 0;   // i 的倍数不是素数
        }
    }

    // 输出所有素数
    printf("Primes up to %d: ", N);
    for (i = 2; i <= N; i++)
    {
        if (sieve[i])
            printf("%d ", i);
    }
    printf("\n");

    return 0;
}

关键优化点：

1. 从 i * i 开始标记：i 的更小倍数（如 2×i, 3×i, ..., (i-1)×i）已经被更小的素数筛过了，无需重复标记。例如 i=5 时，10（2×5）已被 2 筛过，15（3×5）已被 3 筛过，直接从 25（5×5）开始
2. 只处理到 sqrt(N)：与试除法同理——如果 i > sqrt(N)，i 的倍数中最小的 i×i 已经超过 N，没有需要标记的
3. 跳过已标记的数：如果 sieve[i] 已经是 0（非素数），不需要筛它的倍数——因为它的倍数必然已经被它的素因子筛过

复杂度：埃拉托斯特尼筛法的时间复杂度为 O(n log log n)，空间复杂度为 O(n)。对于 n=100，筛法几乎瞬间完成。n=1,000,000 时，筛法在普通计算机上只需约 0.01 秒，而试除法需要数秒。

100 以内的筛法执行过程可视化：

初始:  2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 100
       ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓  ✓  ✓  ✓  ✓  ✓       ✓

i=2: 筛掉 4, 6, 8, 10, 12, 14, 16, 18, 20, ...
     2 3 ✗ 5 ✗ 7 ✗ 9 ✗  11 ✗  13 ✗  15 ✗  ...

i=3: 筛掉 9, 15, 21, 27, 33, 39, ...
     2 3 ✗ 5 ✗ 7 ✗ ✗ ✗  11 ✗  13 ✗  ✗  ✗  ...

i=5: 筛掉 25, 35, 55, 65, 85, 95, ...
i=7: 筛掉 49, 77, 91, ...

最终素数: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (共25个)

---

8. 素数定理、模运算与高级素性测试

8.1 素数定理与素数分布

素数定理（Prime Number Theorem）描述了素数的分布规律。设 π(x) 表示不超过 x 的素数个数，则：

π(x) ≈ x / ln(x)

这意味着：在 x 附近，大约每 ln(x) 个数中就有一个素数。x 越大，素数越「稀疏」：

π(100)   ≈ 100 / ln(100)   ≈ 100 / 4.605 ≈ 21.7  → 实际值: 25
π(1000)  ≈ 1000 / ln(1000)  ≈ 1000 / 6.908 ≈ 144.8 → 实际值: 168
π(10000) ≈ 10000 / ln(10000) ≈ 10000 / 9.210 ≈ 1085.7 → 实际值: 1229

这个定理由高斯（Gauss）和勒让德（Legendre）在 18 世纪末独立提出猜想，最终由阿达马（Hadamard）和瓦莱-普桑（de la Vallée-Poussin）在 1896 年独立证明——是解析数论的巅峰成就之一。

对于编程实践的意义：当你需要生成大素数（如密码学中 1024 位的 RSA 密钥），素数定理告诉你大约每 ln(2^1024) ≈ 710 个数中就有一个素数——随机搜索的期望尝试次数是可控的。

8.2 模运算与费马小定理

当数值变得很大时（如密码学中的 2048 位整数），试除法和筛法都不可行——我们需要概率素性测试（probabilistic primality test）。

费马小定理（Fermat's Little Theorem）：如果 p 是素数，a 是任意不被 p 整除的整数，则：

a^(p-1) ≡ 1 (mod p)

例如：p = 7, a = 2 → 2^6 = 64 ≡ 1 (mod 7)。✓

基于此定理，费马素性测试的思想是：选一个 a，计算 a^(n-1) mod n。如果结果不等于 1，n 一定是合数；如果等于 1，n 可能是素数。

fermat_test_concept.c

// 概念性示例（非完整实现，仅展示思想）
// 费马测试：若 a^(n-1) mod n != 1，则 n 一定是合数
// 注意：存在 Carmichael 数（如 561）能通过所有费马测试但仍是合数
int fermat_test(int n, int a)
{
    // 计算 a^(n-1) mod n（需要快速幂算法）
    // 如果结果 != 1，返回 0（一定是合数）
    // 如果结果 == 1，返回 1（可能是素数）
}

费马测试的问题在于卡迈克尔数（Carmichael numbers）——如 561 = 3×11×17，对几乎所有 a 都满足 a^560 ≡ 1 (mod 561)，但它是合数。

8.3 Miller-Rabin 素性测试（概念介绍）

Miller-Rabin 测试是费马测试的增强版，通过多次随机选择 a 来降低误判概率。它是目前实践中使用最广泛的概率素性测试：

• 如果测试返回「合数」，结果 100% 确定
• 如果测试返回「素数」，误判概率小于 (1/4)^k（k 为测试轮数）。通常 k=40 即可将误判概率降到约 10^-24——比硬件故障概率还低
• 时间复杂度 O(k log³ n)，远优于试除法的 O(√n)

Miller-Rabin 被广泛应用于：

• OpenSSL / GnuTLS 等加密库中的大素数生成
• Java 的 BigInteger.isProbablePrime()
• Python 的 sympy.isprime() 对大数的判断

NOTE

这些高级素性测试超出了本课范围，但了解它们的存在有助于建立完整的知识图谱——从最简单的试除法，到 sqrt 优化，到筛法，再到概率测试，算法效率逐级飞跃。C 语言初学者从试除法起步，随着数学和算法功底的加深，可以逐步接触更高级的方法。

---

9. 素数的实际应用

素数不仅仅是一个数学概念——在现代计算机科学中，它有着至关重要的实际应用：

9.1 RSA 公钥加密

RSA（Rivest-Shamir-Adleman，1977 年）是现代公钥密码体系的基石，其安全性直接建立在大整数分解的困难性之上：

1. 随机选择两个大素数 p 和 q（通常各 1024 位以上）
2. 计算 n = p × q（作为公钥的一部分公开）
3. 攻击者需要将 n 分解为 p × q 才能破解私钥——而目前没有已知的高效算法

如果有一天有人发明了快速的大整数分解算法，整个互联网的安全体系将面临崩溃——这就是素数在当代信息技术中的核心地位。

9.2 哈希函数

许多哈希函数使用素数来减少碰撞（不同输入映射到同一哈希值）。例如：

• 哈希表的大小通常选为素数——因为取模运算 key % prime 的分布比 key % 2^n 更均匀
• Java 的 String.hashCode() 使用素数 31 作为乘数：s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
• 素数乘数能更好地分散哈希值，避免模式导致的聚集

prime_hash_example.c

// 使用素数 31 计算字符串哈希（Java String.hashCode 的 C 语言版本）
unsigned int string_hash(const char *str)
{
    unsigned int hash = 0;
    while (*str)
        hash = hash * 31 + (*str++);
    return hash;
}

9.3 伪随机数生成器（PRNG）

某些伪随机数生成器使用素数作为参数来确保周期长度最大化。例如线性同余生成器（Linear Congruential Generator）：

X_{n+1} = (a * X_n + c) mod m

当 m 为素数时，可以保证生成器的周期达到 m-1（满周期），从而产生更均匀的随机数序列。

9.4 纠错码与有限域

素数在有限域（Galois Field）理论中扮演基础角色。GF(p)（p 为素数）上的运算（加法、乘法模 p）构成了许多纠错码和密码算法的基础——如 Reed-Solomon 编码（用于二维码 QR Code、光盘 CD/DVD 的数据纠错）。

---

参考解答

100 以内最大素数（sqrt + 三层嵌套）

max_prime_sqrt.c

#include <stdio.h>
#include <math.h>

int main(void)
{
    int num;
    int i;
    int max = 0;

    for (num = 1; num <= 100; num++)
    {
        int bound;

        bound = (int)sqrt((double)num);

        for (i = 2; i <= bound; i++)
        {
            if (num % i == 0)
                break;
        }

        if (i == bound + 1)
            max = num;
    }

    printf("max prime is %d\n", max);

    return 0;
}

核心逻辑：外层遍历 1~100，每轮用 sqrt 计算试除上界 bound，然后内层从 2 试除到 bound。如果内层循环完整走完（i == bound + 1），说明没找到约数——num 是素数，更新 max。

注意：这个版本从 1 开始循环，存在一个逻辑漏洞——1 会被误判为素数（详见课堂讨论 Q4）。建议将外层循环改为 for (num = 2; num <= 100; num++)。

不使用 sqrt 的写法（纯整数运算）

max_prime_no_sqrt.c

#include <stdio.h>

int main(void)
{
    int num, i;
    int max = 0;

    for (num = 2; num <= 100; num++)
    {
        for (i = 2; i * i <= num; i++)
        {
            if (num % i == 0)
                break;
        }

        if (i * i > num)    // 等价于 i > sqrt(num)
            max = num;
    }

    printf("max prime is %d\n", max);

    return 0;
}

用 i * i <= num 代替 i <= sqrt(num)，避免 math.h 和 -lm。注意判断条件也变为 i * i > num（等价于内层完全走完）。这种写法不需要浮点运算，对小整数非常高效。循环从 2 开始，避免了 1 被误判为素数的问题。

标志变量写法（更清晰的语义）

max_prime_flag.c

#include <stdio.h>

int main(void)
{
    int num, i;
    int max = 0;

    for (num = 2; num <= 100; num++)
    {
        int is_prime = 1;    // 假设是素数

        for (i = 2; i * i <= num; i++)
        {
            if (num % i == 0)
            {
                is_prime = 0;
                break;
            }
        }

        if (is_prime)
            max = num;
    }

    printf("max prime is %d\n", max);

    return 0;
}

用 is_prime 标志变量替代 i == bound + 1 判断——意图更明确，代码自解释。循环从 2 开始（跳过 1，因为 1 不是素数）。

从大到小 + 跳过偶数的最高效写法

max_prime_efficient.c

#include <stdio.h>

int main(void)
{
    int num, i;

    for (num = 100; num >= 2; num--)
    {
        // 跳过大于 2 的偶数
        if (num > 2 && num % 2 == 0)
            continue;

        for (i = 2; i * i <= num; i++)
        {
            if (num % i == 0)
                break;
        }

        if (i * i > num)    // 是素数！
        {
            printf("max prime is %d\n", num);
            break;           // 找到最大素数，立即停止
        }
    }

    return 0;
}

从 100 往下找，跳过偶数，找到第一个素数（97）就输出并停止。对于「找最大素数」的需求，这是最高效的写法——只需检查 100、99、98、97 四个数。

筛法找出 100 以内所有素数

sieve_all_primes.c

#include <stdio.h>

#define N 100

int main(void)
{
    int sieve[N + 1];
    int i, j;

    // 初始化
    for (i = 2; i <= N; i++)
        sieve[i] = 1;

    // 筛法
    for (i = 2; i * i <= N; i++)
    {
        if (sieve[i])
        {
            for (j = i * i; j <= N; j += i)
                sieve[j] = 0;
        }
    }

    // 输出所有素数
    printf("Primes up to 100: ");
    for (i = 2; i <= N; i++)
    {
        if (sieve[i])
            printf("%d ", i);
    }
    printf("\nTotal: 25 primes\n");

    return 0;
}

输出：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97（共 25 个素数）。

对照检查：sqrt 的返回值是否被转换为 int？判断条件是否正确（i == bound + 1，不是 i == bound）？如果发现约数，是否用了 break 提前退出？编译时加了 -lm 吗？循环是否从 2 开始（避免 1 被误判为素数）？

---

课堂讨论

1. 示例中的 j == tmp + 1 能否改为 j == tmp？为什么？j > tmp 呢？
2. sqrt 是数学库中的函数，除了它还有哪些数学库函数？它们的使用场景是什么？
3. 如果没有数学库（math.h），这个程序应该如何编写效率才能最高？
4. 程序中直接从 1 开始循环：for (num = 1; ...)。1 能作为素数吗？如果考虑这一点，应该怎么修改？
5. 如果要找出 100 以内的所有素数，上面的程序能直接胜任吗？需要什么改动？
6. 埃拉托斯特尼筛法和试除法相比，各自的优缺点是什么？在什么场景下该用哪种方法？

讨论答案

Q1: j == tmp + 1 能否改为 j == tmp？j > tmp 呢？

j == tmp：不能。 当 j == tmp 时，循环条件 j <= tmp 仍为真，循环还会继续执行一轮——所以循环正常结束时 j 不可能是 tmp。

分析 for 循环的退出条件：

for (j = 2; j <= tmp; j++)
    ...

// 循环结束时的 j 值：
// - 遇到 break：j 停留在 break 时的值（满足 ≤ tmp）
// - 正常结束：j++ 到了 tmp + 1，然后条件 j <= tmp 为假，退出

正常结束时 j 必然是 tmp + 1。如果你写 if (j == tmp)，这个条件永远为假（因为正常结束时 j = tmp + 1，而 break 退出时 j 通常是找到约数的位置，也远小于 tmp）。

j > tmp：可以！ 这个写法比 j == tmp + 1 更好——正常结束时 j = tmp + 1 > tmp，break 退出时 j ≤ tmp。j > tmp 不依赖具体的终值，语义上也是「内层循环完整走完了吗」的等价表达。更重要的是，如果未来有人修改循环为 j < tmp 或 j <= tmp - 1，j > tmp 仍然正确，而 j == tmp + 1 则可能失效。

Q2: 除了 sqrt 还有哪些数学库函数？

<math.h> 提供以下常用类别：

类别	函数	用途	示例
幂与根	sqrt、pow、cbrt	平方根、任意次幂、立方根	sqrt(16) → 4.0
三角函数	sin、cos、tan、asin、atan2	角度计算、坐标变换	sin(M_PI/2) → 1.0
双曲函数	sinh、cosh、tanh	工程与物理计算	cosh(0) → 1.0
指数对数	exp、log、log10、log2	自然指数、对数	log(2.71828) ≈ 1.0
取整	ceil、floor、round、trunc	各种取整策略	ceil(3.14) → 4.0
绝对值	fabs	浮点数绝对值	fabs(-3.14) → 3.14
余数	fmod	浮点除法余数	fmod(5.7, 2.0) → 1.7
分解	frexp、modf	分解浮点数为尾数+指数 / 整数+小数	modf(3.14, &intpart) → 0.14

使用场景示例：

math_h_examples.c

#include <math.h>
#include <stdio.h>

int main(void)
{
    // 两点距离
    double dist = sqrt(pow(3.0 - 1.0, 2) + pow(4.0 - 2.0, 2));
    printf("Distance: %.2f\n", dist);  // 2.83

    // 极坐标角度（atan2 自动处理象限）
    double angle = atan2(1.0, 1.0) * 180.0 / M_PI;
    printf("Angle: %.1f degrees\n", angle);  // 45.0

    // 向上取整计算页数
    double pages = ceil(103.0 / 10.0);
    printf("Pages: %.0f\n", pages);  // 11

    // 自然指数
    printf("e^2 = %.4f\n", exp(2.0));  // 7.3891

    return 0;
}

所有数学函数都接受和返回 double 类型。使用时编译加 -lm。

Q3: 没有 math.h 时如何编写最高效？

有三种替代方案，按推荐程度排序：

方案 1（推荐）：i * i <= num 作为循环条件

for (i = 2; i * i <= num; i++)
{
    if (num % i == 0)
        break;
}
if (i * i > num)     // 等价于 i > sqrt(num)
    max = num;

优点：不需要 math.h、不需要 -lm、不需要类型转换、纯整数运算、简洁。缺点：大数时 i * i 可能溢出。

方案 2：i <= num / i 避免溢出

for (i = 2; i <= num / i; i++)
{
    if (num % i == 0)
        break;
}

优点：与方案 1 等价但不会溢出（除法的中间结果不超过 num）。缺点：每次循环多一次除法运算（但对现代 CPU 影响微乎其微）。

方案 3：手动计算 sqrt 上界

int bound = 0;
while (bound * bound <= num)
    bound++;
bound--;    // 回退到满足 bound² ≤ num 的最大 bound

优点：显式计算上界，逻辑直观。缺点：代码较长，每次都要从 0 递增计算。

综合最高效写法（结合从大到小 + 跳过偶数 + 纯整数）：

max_prime_best.c

#include <stdio.h>

int main(void)
{
    int num, i;

    for (num = 100; num >= 2; num--)
    {
        if (num > 2 && num % 2 == 0)
            continue;

        for (i = 2; i * i <= num; i++)
            if (num % i == 0)
                break;

        if (i * i > num)
        {
            printf("max prime is %d\n", num);
            break;
        }
    }

    return 0;
}

Q4: 1 能作为素数吗？从 1 开始循环有问题吗？

1 不是素数。 按现代数学定义，素数是大于 1 的自然数，且只能被 1 和自身整除。1 只有 1 这一个除数（「自身」就是 1），不满足素数定义中「大于 1」的条件。

为什么现代数学把 1 排除在素数之外？根本原因是算术基本定理（Fundamental Theorem of Arithmetic）：每个大于 1 的整数都可以唯一分解为素数的乘积。如果 1 是素数，唯一性就不成立了——例如 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...，分解方式变得无限多。

示例代码中的问题：

当 num = 1 时：bound = (int)sqrt(1) = 1，内层循环 for (i = 2; i <= 1; i++)——条件一开始就为假，内层一次都不执行。i 保持为初始值 2（在 int i; 之后 for 初始化 i = 2 之前，i 的值不确定，但 for 循环的初始化会设置 i = 2；循环不执行意味着 i 停留在初始化的值 2）。而 bound + 1 也是 2，所以 i == bound + 1 成立——max 被错误地更新为 1。

修正方法（任选其一）：

// 方法 1: 循环从 2 开始（最简单）
for (num = 2; num <= 100; num++)

// 方法 2: 显式跳过 1 和更小的数
if (num <= 1)
    continue;

IMPORTANT

这是代码中的一个逻辑漏洞——试除法恰好「放过」了 1（因为没有除数可试），导致被误判为素数。正确的程序应该从 2 开始遍历。这是一个很好的例子，说明边界条件（edge case）需要特别关注。

Q5: 找出 100 以内的所有素数需要什么改动？

当前程序只记录最大素数——每次发现新素数就覆盖 max。要找所有素数，有以下几种方案：

方法 1：直接打印每个素数（最小改动）

for (num = 2; num <= 100; num++)
{
    for (i = 2; i * i <= num && num % i != 0; i++)
        ;

    if (i * i > num)
        printf("%d ", num);   // 直接打印
}
printf("\n");

把 max = num 换成 printf，最小的改动量。

方法 2：存入数组

int primes[100];
int count = 0;

// ... 判断素数逻辑 ...
if (is_prime)
    primes[count++] = num;   // 存入数组

// 输出
for (int k = 0; k < count; k++)
    printf("%d ", primes[k]);
printf("\nTotal: %d primes\n", count);

适合后续需要对素数做进一步处理（如统计、计算间距等）。

方法 3：使用筛法（最高效）

见参考解答中的筛法代码。当要找的素数较多时（如 10000 个），筛法比试除法高效得多。对于 100 以内，性能差异不明显——但养成使用高效算法的习惯很重要。

100 以内的全部素数（共 25 个）：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。

Q6: 筛法和试除法各自的优缺点？什么场景该用哪种？

方面	试除法	埃拉托斯特尼筛法
时间复杂度	O(n√n)（对所有数）	O(n log log n)
空间复杂度	O(1)	O(n)（需要数组）
判断单个数	快（只需 O(√n)）	需要先筛出所有素数
批量找素数	慢（每个数独立判断）	快（一次筛出全部）
内存消耗	几乎为零	需要 n+1 个 int 的数组
实现复杂度	简单	略复杂
适合场景	判断单个/少数几个数是否为素数	找出范围内所有素数

选择建议：

• 只需判断一个数是否为素数 → 试除法（带 sqrt 优化）
• 找出 N 以内的所有素数，N ≤ 10⁶ → 筛法
• 找出 N 以内的所有素数，N 极大但内存有限 → 分段筛法（Segmented Sieve）
• 判断极大数（如密码学中的 1024 位整数） → Miller-Rabin 概率测试

对于本课的练习（100 以内的最大素数），试除法完全足够——但了解筛法的思想为未来处理更大规模的问题打下基础。

---

课后练习

1. 判断用户输入的素数：读取用户输入的一个整数，判断它是否为素数。如果输入不是有效整数，提示重新输入。

   知识点提示：scanf 读整数、试除法判断素数、输入验证（检查 scanf 返回值）、return 从 main 提前退出

2. 统计素数个数：找出 1~1000 以内的所有素数，统计总数并输出。

   知识点提示：遍历 2~1000、双层嵌套、计数器 count++、素数定理 π(1000) ≈ 168 验证结果

3. 分解质因数：读取用户输入的一个大于 1 的整数，输出它的质因数分解结果。如输入 60，输出 60 = 2 * 2 * 3 * 5。

   知识点提示：反复试除同一个约数（while 嵌套 for）、格式输出的末尾处理（去掉末尾的 *）、num /= factor 不断缩小原数

4. 棋盘皇后攻击范围：在 5×5 的棋盘中，用户输入一个位置放置皇后，输出所有皇后能够吃到的位置（按从左到右、从上到下的顺序，0 表示安全，1 表示被攻击，2 表示皇后自身）。

   知识点提示：二维数组、嵌套循环遍历棋盘、水平垂直检查、对角线检查（abs(row - q_row) == abs(col - q_col)）、abs() 需要 <stdlib.h>

5. 哥德巴赫猜想验证：哥德巴赫猜想（Goldbach's conjecture）指出：任意大于 2 的偶数都可以写成两个素数之和。编写程序验证 4~100 以内的所有偶数都满足此猜想，对每个偶数输出一种分解方式。

   知识点提示：嵌套循环穷举、调用素数判断函数、只找到一种分解即可停止（break）、格式输出

练习1: 判断用户输入的素数

check_prime_input.c

#include <stdio.h>

int main(void)
{
    int num, i;

    printf("Enter a number: ");
    if (scanf("%d", &num) != 1)
    {
        printf("Invalid input!\n");
        return 1;
    }

    if (num <= 1)
    {
        printf("%d is NOT prime\n", num);
        return 0;
    }

    for (i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            printf("%d is NOT prime\n", num);
            return 0;
        }
    }

    printf("%d is prime\n", num);
    return 0;
}

关键：用 return 0; 在发现结果后立即退出——main 函数的 return 可以直接结束程序（不必用 break 跳出多层嵌套）。这在只做单一判断的场景中比 break 更简洁。

练习2: 统计素数个数

count_primes.c

#include <stdio.h>

int main(void)
{
    int num, i, count = 0;

    for (num = 2; num <= 1000; num++)
    {
        int is_prime = 1;

        for (i = 2; i * i <= num; i++)
        {
            if (num % i == 0)
            {
                is_prime = 0;
                break;
            }
        }

        if (is_prime)
            count++;
    }

    printf("primes count = %d\n", count);   // 输出 168

    return 0;
}

答案：1~1000 中共有 168 个素数。可以用素数定理验证：1000 / ln(1000) ≈ 1000 / 6.908 ≈ 144.8，实际值 168——随着 N 增大，近似会越来越准。

练习3: 分解质因数

prime_factorization.c

#include <stdio.h>

int main(void)
{
    int num, factor;
    int first = 1;    // 控制是否输出 " * " 前缀

    scanf("%d", &num);

    printf("%d = ", num);

    for (factor = 2; factor <= num; factor++)
    {
        while (num % factor == 0)
        {
            if (!first)
                printf(" * ");
            printf("%d", factor);
            first = 0;
            num /= factor;       // 不断除以这个因子
        }
    }
    printf("\n");

    return 0;
}

注意使用 while 而非 if——同一个质因子可能多次除（如 12 = 2 × 2 × 3，2 要除两次）。num /= factor 不断缩小原数，直到被除尽。first 标志变量控制格式——第一项前面没有 *，后续项前面加 *。

练习4: 棋盘皇后攻击范围

queen_attack.c

#include <stdio.h>
#include <stdlib.h>   // abs()

int main(void)
{
    int board[5][5] = {0};
    int q_row, q_col, i, j;

    scanf("%d %d", &q_row, &q_col);
    q_row--; q_col--;    // 转为数组下标（用户输入从 1 开始）

    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 5; j++)
        {
            if (i == q_row && j == q_col)
                board[i][j] = 2;     // 皇后自身
            else if (i == q_row || j == q_col)
                board[i][j] = 1;     // 同行或同列
            else if (abs(i - q_row) == abs(j - q_col))
                board[i][j] = 1;     // 对角线
        }
    }

    for (i = 0; i < 5; i++)
    {
        for (j = 0; j < 5; j++)
            printf("%d ", board[i][j]);
        printf("\n");
    }

    return 0;
}

皇后攻击范围：同一行、同一列、同一对角线。对角线的数学特征——两个位置到皇后位置的行差绝对值与列差绝对值相等（|Δrow| == |Δcol|）。abs() 来自 <stdlib.h>，用于计算绝对值。

练习5: 哥德巴赫猜想验证

goldbach_verification.c

#include <stdio.h>

// 判断 n 是否为素数
int is_prime(int n)
{
    int i;
    if (n <= 1) return 0;
    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}

int main(void)
{
    int even;

    for (even = 4; even <= 100; even += 2)   // 只遍历偶数
    {
        int p;
        for (p = 2; p <= even / 2; p++)
        {
            if (is_prime(p) && is_prime(even - p))
            {
                printf("%d = %d + %d\n", even, p, even - p);
                break;   // 找到一种分解方式即可
            }
        }
    }

    return 0;
}

哥德巴赫猜想至今未被证明——但在已验证的范围内（远大于 100）都成立。这个程序验证了 4~100 内所有偶数都可以分解为两个素数之和。内层循环穷举第一个素数 p，第二个素数通过 even - p 计算——不需要双重嵌套来穷举两个素数。

---

参考资料

• ISO C99 Standard, Section 7.12 — 数学库 <math.h> 中所有函数的完整规范，包括精度要求与错误处理
• Prime Number Theorem — 素数分布与 n/ln(n) 近似公式，从高斯猜想到阿达马证明的历史
• Sieve of Eratosthenes — 埃拉托斯特尼筛法的详细分析、复杂度证明与分段筛法扩展
• Miller–Rabin primality test — 现代概率素性测试的原理与误判率分析
• GNU C Library: Mathematics — libm 的详细文档，包括 IEEE 754 舍入模式与异常处理
• Euclid's Elements, Book IX, Proposition 20 — 欧几里得素数无穷性证明的原文与注解

"There's always more to learn, and there are always better ways to do what you've done before." — Donald Ervin Knuth