计算器怎样找到下一个质数

数列中标出输入值之后第一个质数的示意图

输入非负整数n，计算器会找出严格大于n的第一个质数p，并给出差值p - n以及实际检查过的奇数候选数量。

为什么不把输入值本身作为答案

“下一个”对应条件p > n。即使输入17本身是质数，结果也会是19。这里也不会比较n左侧的质数，因此与“最近的质数”不是同一个问题。

p = \min \{q \in \mathbb{P} \mid q > n\}

搜索从n + 1开始。n小于2时，首先考虑2；超过2以后可以跳过偶数，因为所有大于2的偶数都是合数。

合数的两个因数不可能同时大于它的平方根，所以检查到这一界限已经足够。整个过程使用精确整除，不需要四舍五入。

n = 0时结果为2，差值为2，候选数为1。n = 1时结果仍为2，但差值变成1。

n = 14时先检查15。15能被3整除，因此继续检查17。最终p = 17，差值为3，共检查2个奇数候选。

n = 1000时依次检查1001、1003、1005、1007和1009。前四个是合数，1009是质数，因此差值为9，候选数为5。

相比之下，n = 100时第一个候选101就是质数。输入数值大，并不一定意味着搜索过程长。

差值计算n到p之间的完整距离。候选数只统计真正进行质数判断的奇数，不包括预先跳过的偶数，也不等于除法运算次数。

合数可能被较小因数立刻排除；质数则需要检查完整的平方根范围。

输入范围为0至1,000,000,000,000。输入上限时，下一个质数是1,000,000,000,039，差值39，共检查20个奇数候选。上限限制的是n，因此p可以略大。

小数、负数和空值无效。数百位的大整数需要专用的大整数类型和质数算法，不属于本工具的范围。

理解严格大于、单向搜索和候选计数后，就能避免大多数误判。

仍会继续向后搜索。输入29时返回31，而不会重复29。

不一定。最近的质数可能小于n，本计算器只寻找大于n的数。

质数必须恰好有两个正因数。1只有一个正因数，因此它之后的第一个质数是2。

不会。除2以外的偶数都是合数，可以直接跳过。

可以。一万亿是输入上限，它之后的第一个质数是1,000,000,000,039。

确认p大于n，中间整数都是合数，并检查p在平方根以内没有可整除的因数。

以下与此主题相关的计算器可能对您有用：

如果您喜欢，请在您的社交媒体平台上分享计算器。对您来说很简单，对项目的推广很有帮助。谢谢！

差值 p - n	1
已检查的奇数候选	1