梯形法把面积切成 n 条竖条，每条当梯形算，加起来就是近似值。 块数乘 10，误差除 100——误差跟每块宽度的平方成正比，这是二阶的节奏。 埃氏筛把倍数一个个划掉：只筛到根号 N，而且从 i 的平方开始划。
上一篇解方程，这一篇算面积和找质数，看起来毫不相干，但都是「用笨办法逼近正确答案」。 梯形法代表「切成小块、逐块累加」这一整类算法——积分、微分、仿真，底子都是它。 埃氏筛代表另一类：用一张表标记「已经排除掉的」，剩下的就是答案。
一、梯形法：把面积切成一堆小梯形
要算 y = x 的平方 从 0 到 1 这段曲线下面的面积。答案是 1/3，但直接算算不出来。
梯形法的做法：把这段横着切成 n 条，每条曲边梯形当成直边梯形算——（上底 + 下底）除以 2 再乘高。
然后把 n 条加起来。条数越多，每条的曲边就越短、越接近直线，结果越准。
演示里切 10 条得 0.335，误差 1.67e-3；切 100 条误差 1.67e-5；切到 10000 条，误差 1.67e-9。 注意切 10 条时算出来是 0.335，比真值 1/3 大一点。 这也不是巧合，曲边梯形被当成直边梯形时面积总是估大（对这条曲线而言）。
二、块数乘十，误差除一百
看演示里那张表的第三列：1.67e-3、1.67e-5、1.67e-7、1.67e-9。每一行都是上一行的百分之一。 块数只乘了 10，误差却除了 100。这说明误差跟每块宽度的平方成正比，不是跟宽度本身成正比。 演示里那句注解写的是「降到十分之一、一阶精度」，和表里的数对不上。 以表为准：这里表现出来的是二阶。
为什么是平方？ 因为梯形法主要的误差来自「用直线代替曲线」，而这一小段里直线与曲线的偏离量跟段宽的平方有关。 段宽减半，偏离减到四分之一。 数值计算里这是标准结果：复化梯形公式的误差是步长的平方量级。 记住「平方」两个字，比记某个具体系数有用。
三、但工程上还是觉得不够快
二阶听着不错，可它意味着想多准一位，块数得乘三倍多（因为 3 的平方约等于 10）。 要三位小数变六位，块数得乘三十倍。 所以实际计算积分很少直接用梯形法，改用辛普森法这类更高阶的方法。 辛普森法的思路是用抛物线去贴合曲线，而不是用直线。 曲线贴曲线，误差掉得快得多——它每块宽度减半，误差能减到十六分之一。
对本课来说，梯形法的价值不在实用，在示范： 「切成小块、逐块算、再加起来」这个套路本身就是一大类算法的骨架。 而且它有个无可替代的优点：什么曲线都能用。只要知道每一点的函数值，管你函数长什么样——实测数据、 查表值都行。
四、埃氏筛：把倍数一个个划掉
找 100 以内的质数。 做法：写下 2 到 100，从 2 开始， 把 2 的倍数全划掉；再找下一个没被划的 3，把 3 的倍数划掉；以此类推。 没被划掉的剩下的就是质数。演示里列出来 25 个，从 2 到 97。 为什么这招管用？ 因为一个合数一定能写成两个更小的数相乘，那它必然是自己某个质因子的倍数，早就被划掉了。
所以「划掉倍数」等于「排除所有合数」。剩下的自然全是质数。 这个方法比「每个数都试除一遍」快得多——它不判断，只标记。判断要算，标记只是打个勾。
五、划掉了 74 个，这个数怎么来的
演示里说 100 以内划掉了 74 个合数。这个数不是数出来的，是算出来的： 0 到 100 一共 101 个数，去掉 25 个质数，再去掉 0 和 1，剩下 74 个。 为什么要单独去掉 0 和 1？因为这两个数既不是质数也不是合数。这是定义决定的，不是算法决定的。
这类「边界数字」在算法里总要单独处理：0、1、负数、空集， 每次写算法都得问一句「这几个特殊值走哪条路」。 演示里那张表还给出了每一轮划掉几个：49、31、16、8。 数字越来越少，因为越往后，它的倍数里有越多已经被更小的质数划过了。
六、两处优化：只筛到根号，从平方开始
演示末尾那两句是埃氏筛的精髓。 第一处：只筛到根号 N 就够了。100 的根号是 10，筛到 7 就停。 为什么？因为一个合数一定有个因子不超过根号。 如果两个因子都大于根号，它们的乘积就超过 N 了——不可能。
第二处：从 i 的平方开始划，不是从 2i。因为比 i 小的那些倍数（2i、3i……）早被更小的质数划过了。 这两处优化加起来，把「能算」变成了「算得快」。算法的改进往往不是换思路，是少做重复的活。
七、动手 Demo：把面积切成条，把倍数一个个划掉
先用梯形法算 y = x 的平方 在 0 到 1 上的面积，切 10、100、1000、10000 条各算一次。
再用埃氏筛求 100 以内的质数，把每一轮划掉几个也打出来。
def trap(n):
h = 1.0 / n
s = (0.0 ** 2 + 1.0 ** 2) / 2
for i in range(1, n):
s += (i * h) ** 2
return s * h
for n in (10, 100, 1000, 10000):
v = trap(n)
print(n, '%.8f' % v, '%.2e' % abs(v - 1 / 3))
N = 100
is_p = [True] * (N + 1)
is_p[0] = is_p[1] = False
cut = 0
for i in range(2, int(N ** 0.5) + 1):
if not is_p[i]:
continue
c = 0
for j in range(i * i, N + 1, i):
if is_p[j]:
is_p[j] = False
c += 1
cut += c
print('筛', i, '这一轮划掉', c)
prime = [i for i in range(N + 1) if is_p[i]]
print(prime)
print('共', len(prime), '个质数，划掉', cut, '个')
实跑输出：
--------------------------------------------------------------------
梯形法与埃氏筛
--------------------------------------------------------------------
① 梯形法：把面积切成一堆小梯形
--------------------------------------------------------------------
| 切成几块 | 算出来的面积 | 和 1/3 的差 |
|---:|---:|---:|
| 10 | 0.33500000 | 1.67e-03 |
| 100 | 0.33335000 | 1.67e-05 |
| 1000 | 0.33333350 | 1.67e-07 |
| 10000 | 0.33333333 | 1.67e-09 |
真值 1/3 = 0.33333333
把曲线下方切成 n 条竖条，每条当成梯形：(上底 + 下底) / 2 × 高。加起来就是面积的近似值。
看第三列：块数乘 10，误差也差不多降到十分之一。
这叫一阶精度——想多一位小数就要多十倍的块数，很贵。所以工程上会用更聪明的办法（辛普森法）代替。
! 这里算的是 y = x² 从 0 到 1 的面积，答案是 1/3。
教材用梯形法算的是同一个思路，只是被积函数不同。
② 埃氏筛：把倍数一个个划掉
--------------------------------------------------------------------
找 100 以内的质数：[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 个，划掉了 74 个合数
74 是从 0 到 100 一共 101 个数算出来的：去掉 25 个质数，再去掉 0 和 1，剩下 74 个合数。
| 步骤 | 做什么 | 这一轮划掉几个 |
|---|---|---:|
| 从 2 开始 | 2 是质数，划掉 4、6、8… | 49 |
| 下一个没被划的 3 | 划掉 9、12、15… | 31 |
| 下一个 5 | 划掉 25、30… | 16 |
| 下一个 7 | 划掉 49、56… | 8 |
只筛到根号 N 就够了：一个合数一定有个不超过根号的因子。
100 的根号是 10，筛到 7 就停，剩下的没被划掉的全是质数。
而且从 i 的平方开始划，不是从 2i：比 i 小的倍数早被更小的质数划过了。
这两处优化，就是埃氏筛能从「能算」变成「算得快」的原因。
①trap 里先把两头的端点各算一半，再累加中间的点，最后乘高。
这是梯形法的通用写法，也省掉了一个循环。
②误差那列用 %.2e 打成科学记数，方便看数量级变化。
③筛法里 for j in range(i * i, N + 1, i) 就是从 i 的平方开始，
步长是 i——正好跳过 2i、3i 这些早被划过的。
④if is_p[j] 那个判断是为了只数「第一次被划掉」的，不然同一个合数会被数好几次。
30 秒实验
- 把
trap的块数从 10000 再乘十，看误差还降不降（会碰到浮点精度上限）。 - 把筛法的
range(i * i, ...)改成range(2 * i, ...)，看质数表还对不对、划掉几个变不变。 - 把筛法上限改成 1000，看质数有几个（提示：168 个）。
常见误区
- 「梯形法块数越多越准，所以一直加。」块数太大时浮点误差会盖过理论精度，加也没用。
- 「1 是质数。」1 既不是质数也不是合数，所以筛完要去掉 0 和 1。
- 「筛法要筛到 N。」筛到根号 N 就够，比它大的数不可能是更小数的倍数。
自测三问（点开对答案）
1. 梯形法的误差跟块数什么关系？ —— 跟每块宽度的平方成反比：块数乘十，误差除一百。这是二阶，比一阶快但想再多一位仍要加不少块。 2. 埃氏筛为什么能把合数划干净？ —— 合数一定能写成两个更小的数相乘，必然是某个质因子的倍数，早被划掉了。 3. 为什么只筛到根号 N？ —— 合数必有一个因子不超过根号 N。两个因子都大于根号，乘积就超过 N 了。最后一节讲两个「元」话题：函数怎么调用自己，和算法怎么画成图。 前者是很多算法的写法，后者是写代码之前该做的事。
- ☐ （本篇完，下一篇 7.3 递归、算法与流程图）