素数实验室
ALGORITHM / 01 · C 语言入门
把抽象的代码,变成看得见的过程

一个数,怎样成为素数?

跟着变量走一遍:从尝试、判断,到把一个新素数放进数组。

2, 3, 5, 7, …

执行现场

初始化

变量观察窗

值 · 作用 · 所在作用域

素数收集盒 prime[]

代码与执行同步

C99

终端输出

每行 5 个

程序运行到 printf 时,输出会出现在这里。

空格 播放 / 暂停 · ← → 单步
读懂三个最容易混淆的地方

prime[count++] = i:使用 count 的旧值作为下标,再令 count 加 1。演示拆成两步,便于观察;这是一种教学等价展开。

main 的 i → x:传入的是数值副本。函数内的 i 是另一个局部变量,代表数组下标,不会改变 main 的 i。

prime → knownPrimes:数组参数传递的是首元素地址,二者访问同一组元素;count → numberOfKnownPrimes 则是数量的值拷贝。

为什么只用已知素数试除?

每个大于 1 的合数都至少有一个素因子。我们从 3 开始按顺序测试,因此判断 x 时,所有比 x 小的素数都已经找到;有任何一个整除 x,就可以排除它。

这段 isPrime 依赖“从 3 开始顺序生成”和“素数表完整”的前提,不能拿任意 x 和不完整的表来通用判定。本课忠于材料,试除全部已知素数;没有加入平方根剪枝。

2 是最小素数;小于 2 的整数既不是素数,也不是合数。

原材料校正:时间、内存与 C 语言

循环反复更新同一个变量,不会为每一个除数累积占用内存。两种单次判断都只需常数级额外空间;保存前 n 个素数的数组需要 O(n) 空间。逐个试除较慢,是因为取余运算次数更多。

为确保在 C99 下可编译,这里用 enum { number = 10 }; 表示固定数组长度。普通局部 const int number 在 C 中并非整型常量表达式,不能照原文方式初始化变长数组。

int prime[number] = {2}; 会把剩余元素置为 0。0 是空闲槽位的初始值,不代表已找到的素数。逐个试除法的未初始化槽位则显示“—”,不会读取它们。

停下来,想一想

如果 count = 3、main 的 i = 7,执行 prime[count++] = i 后,发生了什么?