一个数,怎样成为素数?
跟着变量走一遍:从尝试、判断,到把一个新素数放进数组。
执行现场
初始化变量观察窗
值 · 作用 · 所在作用域素数收集盒 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 后,发生了什么?