质数计算器

n 是质数 ⟺ d(n) = 2；previousPrime(97) = 97；nextPrime(97) = 97；nextPrime(1000000) = 1000003

n

被判定的那个整数，取 2 到 1000000。下界是刻意抬上去的，不是沿用内核的：previousPrime(1) 这个量不存在，一个收下 1 的页面会有一行没法老实填出来。「1 是不是质数」是定义问题，答案写在下面的问答里，不写在计算器里

d(n)

正因数的个数，也就是结果的第一行，也是判定所依据的全部证据。d(n) = 2 表示恰好有两个数能整除它，这正是质数的定义。这个数来自共用的数字论模块，所以它与因数计算器、质因数计算器对同一个输入报出的值是同一个

d(n) = 2

判定本身，写成一条等价关系。它是「当且仅当」而不是近似：一个数有且只有两个正因数，当且仅当它是质数。97 的正因数是 1 和 97，所以个数是 2，徽章读作质数。100 的正因数是 1、2、4、5、10、20、25、50、100，一共九个，所以徽章读作合数

previousPrime(n)

不大于 n 的最大质数。它在上面那一端是闭的，所以 n 本身是质数时答案就是 n。100 的答案是 97，25 的答案是 23，97 的答案是 97。取闭区间是因为换成开的就得规定「n 已经是质数时印什么」，而结果面板上的一格空白读起来是出错，不是事实

nextPrime(n)

不小于 n 的最小质数，下面那一端同样取闭区间。25 的答案是 29，100 的答案是 101，97 的答案是 97。这一个可以走出输入范围：nextPrime(1000000) 是 1000003，比页面接受的任何输入都大，页面把它当作答案报出来，而不是当作越界拒掉

1e6 到 1e6 + 100

输入上界附近的那一片，以及为什么那儿需要第二份判定。一百万附近的质数是 999983 与 1000003，所以从 1000000 出发的搜索有一个方向要越过一百万。数因数的那个例程不接受一百万以上的参数，会直接抛错，所以近邻搜索用了自己那份没有上限的判定——两份判定在重叠的地方必须一致，参考表里 97 那一行就是这条一致性

挑模数是想找一个数附近的质数最实际的动机。哈希表的槽位数通常取质数，因为质数模数会把共享公因数的键摊开，而不是让它们撞在一起：一张一千格的表会把所有 25 的倍数塞进同一小片位置，而 997 格的表不会。密码学里的用法同理，密钥由又大又彼此远离的质数搭成。判断一个数是不是质数还能把整除问题一次问完：如果一个数在它的平方根以内没有质因数，那它整个就没有质因数，徽章一步就回答了这件事，不必逐个试。还有些问题本身就是关于质数的——孪生质数、相邻质数之间的间隙、以及某个数是不是两个质数之积。当问题转成「它由哪些质数乘出来」的时候，质因数计算器把分解式给出来，那是自然的下一站；当问题转成「哪些数能整除它」的时候，因数计算器把清单列出来；而当被判定的那个数不是质数、你想知道它是什么搭成的时候，本页印出的正因数个数是第一条线索，而不是完整的答案。

1. 一个质数：97

   1. 试除 97 的因数：2 除不尽，3、5、7、11 也都除不尽
   2. 试到平方根就停：10 × 10 = 100 已经超过 97，再往下没有可试的了
   3. 正因数只有 1 和 97，所以个数是 2，这个数是质数
   4. 上一个质数是 97 自己，因为 97 已经是质数，而搜索取的是闭区间
   5. 下一个质数同样是 97，理由一样

   默认输入，也是闭区间规则最干净的一例。两个近邻都印成这个数本身，看上去像是那两行什么都没做。它们做了：不大于 97 的最大质数是 97，不小于 97 的最小质数也是 97。换成严格不等号，这两行就会偏偏在页面最有把握的输入上无字可印，而结果面板里的一格空白读起来是错误。这一格也是页面上两份判定相遇的地方：数因数的那份说 2，找近邻的那份也认为 97 是质数，而它们走的是两段不同的代码。

2. 一个合数：100

   1. 100 是偶数，所以 2 能整除它；它末尾是 00，所以 4、5、10、20、25、50 也都能整除它
   2. 正因数是 1、2、4、5、10、20、25、50、100，一共九个
   3. 九个比两个多，所以徽章读作合数而不是质数
   4. 不大于 100 的最大质数是 97，不小于它的最小质数是 101
   5. 两个近邻各在它一侧，这就是一个数落在质数间隙中间的样子

   这一格让两个近邻真正派上用场。一个数合数时，那两行才是有用的输出，因为它们回答了读者紧接着的问题：既然不是这个数，那该是哪个？97 与 101 是最近的质数，而 100 就夹在中间。九个正因数也值得看一眼——它是奇数，而正因数个数是奇数这件事，恰好只在完全平方数上发生，100 正是 10 的平方。所以扫一眼这个数就已经知道这个数的形状了，用不着先做分解。

3. 紧挨着一个质数：25

   1. 25 的正因数是 1、5、25，一共三个，因为 5 与自己配对
   2. 三个比两个多，所以 25 是合数
   3. 从 25 往下走：24、23——23 是质数，所以它是上一个质数
   4. 从 25 往上走：26、27、28、29——29 是质数，所以它是下一个质数
   5. 这里的间隙一共是六：23 与 29 一左一右夹着 25

   一个完全平方数，所以正因数个数是奇数；也是两个近邻明显不等距的一格——下面差二、上面差四。个数是 3 这件事还说明为什么门槛取在 2 而不是「质因数有几个」：25 只有一个质因数 5，但它不是质数，而正因数个数直接抓到了这一点，根本不用去看分解式。

输入必须是 2 到 1000000 之间的整数。0 与 1 会被拒绝，而拒绝 1 的理由与拒绝 0 不同：那是一条定义问题，不是越界，而且 previousPrime(1) 根本不存在。负数会被拒绝——质性是大于 1 的整数才有的性质，虽然数学的某些分支里对负质数有约定，本页不采用。小数一律拒绝而不是四舍五入。一百万这个上界只约束输入，不约束答案：两行近邻可以正当地报出一个超出它的质数，而一百万的下一个质数 1000003 会被照实印出来，不会被拒。判定用的是试除法，试到平方根为止，在这个量级上是瞬间的事，在一个二十位数上则毫无希望，而这条边界是问题本身的性质，不是这份实现的毛病。页面给出三个数加一枚徽章：它不列出因数清单本身，不分解合数，也不一次判定一串数。下面两张参考表是固定的行，不跟着你的输入走。最后，质数被报成它自己的上一个与下一个质数，这是刻意取闭区间的结果，不是两行没找到东西。

1 是质数吗？

不是，而且它也不是合数。质数的定义是大于 1、恰好有两个正因数的整数，而 1 只有一个正因数，两头都不符合。这是刻意定的规矩而不是疏忽：如果 1 算质数，那么「每个数只有一种质因数分解」这句话就不成立了——你可以往任何一个分解式上乘任意多个 1。把 1 排除在外，正是为了让那条定理说得干净。因为这是定义问题而不是算术问题，页面不收 1 这个输入，答案写在这里而不是印在结果面板上。

为什么上一个质数和下一个质数都印成这个数自己？

因为两边的搜索都取闭区间。上一个质数是不比你输入的那个数更大的最大质数，下一个质数是不比它更小的最小质数。当输入自己就是质数时，它同时满足这两句话，所以两行都报它。换成严格不等号的话，输入是质数时就会有两行无字可印，而结果面板里的一格空白读起来像是出了错——页面偏偏在最确定的这一格上答不上来。同一条纪律也出现在四舍五入里：已经在目标精度上的数原样返回。

为什么下一个质数可以超过一百万，而输入不能？

因为那个上限约束的是你能问什么，不是答案能落在哪里。一百万的下一个质数是 1000003，拒绝印它，等于拒绝回答一个关于页面已经收下的输入的、完全说得通的问题。所以找近邻用的是自己那份没有上界的判定，而数正因数的那份仍然用只覆盖量程的内核例程。这确实意味着有两处逻辑都在判断一个数是不是质数——一处带量程、一处不带——而它们必须在重叠的地方给出同样的答案，97 那一格查的就是这件事：个数说 2，找近邻的那份也说 97 是质数。

质数到底有什么用？

多半是拿来定尺寸的。哈希表通常取质数格数，因为质数模数会把共享公因数的键摊开——一千格的表会把所有 25 的倍数推进同一小片位置，而 997 格不会。凡是计数要绕圈的地方都是同一个道理：循环长度取质数，就不会跟数据里周期性的规律共振。另一个大去处是密码学，密钥由又大又彼此远离的质数搭成，安全性正建立在「把它们的乘积分解回那两个质数」有多难之上。小一些的用处到处都是：核一句整除的断言，判断一个数是不是两个质数之积，以及孪生质数、相邻质数间隙这类经典问题。

页面是怎么判定的，结论有多可靠？

靠数正因数，这是精确判定而不是概率判定。一个数是质数当且仅当它恰好有两个正因数，所以这个个数把问题彻底问死，既没有答错的可能，也不需要去信一个可能被蒙过去的检验。数的办法是试除法，试到平方根为止，这也是量程停在一百万的原因：再往上这个方法变得很慢，而不是变得不准。对更大的数，精确方法确实不现实，人们改用概率检验；但在现在这个量级上，没有任何理由接受一个不如「确定」的答案，页面也就没接受。

为什么要把正因数个数印出来，而不是只给一个结论？

因为这个个数就是结论的理由，把它印出来，两者就永远不会打架——徽章不是第二次计算，而是对旁边那个数的一次读数。它自己也派得上用场。个数是奇数说明这个数是完全平方数，因为平方根与自己配对而不与另一个因数配对。个数是 2 就是质数的定义。个数相对于这个数的大小显得很大，说明它有很多小因数，是那种很快就能攒出一堆因数的数。它还把这个页面跟别的页面连起来：质因数计算器对同一个输入报出同一个正因数个数，只是它是从指数连乘算出来的，两页正好互相印证。

• 质数——质数的定义、正因数个数这条判据，以及 1 为什么被排除在外 — 维基百科（中文）
• Prime Number —— 质数的定义、正因数个数这条判据，以及 100 以内那二十五个质数 — Wolfram MathWorld（美国）
• Prime Gaps —— 相邻两个质数之间的距离，以及一百万附近那一片长什么样 — Wolfram MathWorld（美国）
• 教育部关于印发义务教育课程方案和课程标准（2022 年版）的通知——附件清单第 5 项为《义务教育数学课程标准（2022 年版）》；质数与合数是小学高年级数与代数领域的内容，原文与学段要求以该附件为准 — 中华人民共和国教育部