素数的筛子与森林
素数像森林里的树：开始很密，越往里越稀，却永远走不到尽头。先用筛子把它们筛出来，再去看看这片森林的分布地图。
为什么不用除到 n？
想一想📐因数总是成对出现
如果 n = a × b，那么 a 和 b 是一对。除非 a = b = √n，否则总有一个小于 √n、一个大于 √n。
所以只要在 2 到 √n 之间找不到因数，n 就不可能被分解——它就是素数。
⚡还能更快
先只用小素数试除；再跳过所有 2、3 的倍数，只试 6k±1 形式的数；要判断几百位的大数，则用米勒–拉宾（Miller–Rabin）概率检测，几毫秒就能给出“几乎确定”的答案。
RSA 加密就建立在大素数容易找、但大数分解很难这件事上。
🎭费马检测会“被骗”
有些合数也能让 2n−1 ≡ 1 (mod n)，它们叫“卡迈克尔数”，比如 341、561、1105、1729。
所以费马检测只能用来排除合数：余数不是 1 就一定不是素数；余数是 1 也不能完全确定。
🎯小挑战
① 101 是素数吗？② 221 是素数吗？
③ 为什么判断 97 时，只需要试 2、3、5、7？
看答案
① 是（试到 √101≈10，2、3、5、7 都除不尽）；② 不是，221=13×17；③ √97≈9.8，小于 10 的素数只有 2、3、5、7。
筛法的聪明之处
想一想🧹不重复劳动
划 2 的倍数时，4、6、8……都没了；轮到 3 时，从 3×3=9 开始划就够了，因为 6 已经被划掉。
每个合数只会被它的最小素因数划掉一次，效率很高。这就是为什么筛 100 万以内的素数只要一瞬间。
🏛️两千年前的算法
埃拉托斯特尼（Eratosthenes）是古希腊的图书馆长，他用这张“筛子”找素数，还第一个比较准确地测出了地球周长。
这个算法到今天还在用，只是换了更快的实现。
⏱️筛法有多快？
筛到 N 大约需要 N log log N 次操作。筛到 100 万是眨眼的事；筛到 10 亿，普通电脑也就几秒钟。
但如果 N 大到 10¹²，就需要分段筛、甚至更聪明的数论方法了。
🎯小挑战
① 筛到 100 时，最后一个用来划掉的素数是几？
② 100 以内有多少个素数？
看答案
① √100=10，所以只用到 7（2、3、5、7 筛完即可）；② 25 个。
素数森林的四个秘密
想一想🌲越走越稀，但走不到头
欧几里得用反证法证明了素数有无穷多个：假设只有有限个，把它们乘起来再加 1，得到的数要么本身是素数，要么有新的素因数——矛盾。
密度约 1/ln n：n 越大，遇到素数的概率越小，但永远不会变成 0。
👯孪生素数
相差 2 的素数对叫孪生素数：3 和 5、11 和 13、41 和 43……它们有没有无穷多对？至今没人能证明。
2013 年，张益唐证明了“相差不超过 7000 万的素数对有无穷多对”，这是重大突破。
🌀乌岚螺旋的斜线
把自然数排成螺旋再标出素数，会看到一些明显的斜线。这是因为对角线上的数形如 4k²±2k+1 这类二次多项式，有时更容易是素数。
注意：这是“图案”，还不是“规律”。素数没有已知的简单生成公式。
🔐素数有什么用？
RSA 加密：找两个大素数相乘很容易，但把乘积分解回两个素数极其困难。你的每一次网上支付，背后都站着两个很大的素数。
大素数检测用米勒–拉宾算法；而“大数分解”至今仍是难题。数学的“难”，成了安全的基石。