素数判断器

什么是素数?什么时候需要判断?

素数(也叫质数)是大于1、且只能被1和它本身整除的自然数。7只能被1和7整除,所以是素数;8能被1、2、4、8整除,所以不是素数。 大于1且不是素数的自然数叫合数。约数与倍数的作业、编程时选择哈希表长度或取模的数、日历与周期类的谜题、素数检验的编程练习,都常会用到。 本工具可以判断单个数是否为素数,是合数时给出质因数分解,并列出10,000以内的全部素数。

判断原理:只需除到平方根

如果n是合数,就可以写成 n = a × b(1 < a ≤ b)。因为a不大于b,所以 a² ≤ n,即 a ≤ √n。 因此合数在√n以内一定有一个不是1的因数。从2试除到√n,如果没有任何数能整除n,就可以断定n是素数。 本工具还做了精简:先处理2,然后只用3、5、7……这些奇数去除,因为偶数在2的检查中已经被排除。

素数判断:在 2 ≤ d ≤ √n 的范围内,没有任何d能整除n,则n为素数

这只是普通的试除法,没有使用BigInt,也没有使用米勒-拉宾这类概率性检验。计算基于普通的JavaScript数值, 能精确表示的整数最大到2^53 − 1(约9千万亿),本工具接受的上限是10^15(1千万亿)。最坏的情况是接近10^15的素数,需要约1600万次除法, 在台式机上试了约0.1秒,实际速度因设备而异。列表功能对范围内的每个数做同样的判断。 范围很大时,逐个划掉素数倍数的埃拉托色尼筛法要快得多,下面的表格就是构建页面时用这种方法算到100万得到的。

100以内的25个素数

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

1,000以内有35对孪生素数(相差2的素数,如3和5、5和7、11和13)。另一方面,相邻素数之间的间隔在某些地方会变大。 下表列出间隔纪录首次达到6、8以及14以上的位置,每行给出该素数和它后面的下一个素数。

素数有多少:π(x)参考表

不超过x的素数个数记作π(x)。素数定理指出,x越大,π(x)越接近 x / ln x。下表对比了实际个数与这个近似值。

10,000以内共有1,229个素数,所以列表功能最多显示1,229个。数越大素数越稀疏,但素数有无穷多个(欧几里得已证明)。

验算过的示例

示例1:97。√97 ≈ 9.85,只需试除3、5、7、9。都不能整除,所以97是素数。

示例2:91。这是常被误认为素数的数。它不能被3、5整除,但91 ÷ 7 = 13,即 91 = 7 × 13,是合数。

示例3:360的质因数分解。2^3 × 3^2 × 5。合数可以唯一地(不计顺序)表示为素数之积,这就是算术基本定理。

示例4:2^31 − 1 = 2,147,483,647。这个梅森数是素数。判断时只需用√n ≈ 46,340以内的23,169个奇数去试除。 一个超过20亿的数,约两万三千次除法就能判定。

常见误解与局限

• 1不是素数。定义要求“大于1的自然数”。如果把1算作素数,质因数分解就不再唯一(6 = 2×3 = 1×2×3……)。
• 2是唯一的偶素数。其他偶数都能被2整除,都是合数。
• 不能只看个位数。以1、3、7、9结尾的数也可能是合数(如91、119、143)。
• 素数不都是奇数。因为有2,所以“素数都是奇数”的说法是错的。
• 不支持特别大的数。本工具用试除法判断10^15以内的整数,无法检验几百位的数,也不能生成密码学用的素数。
• 素数列表最多到10,000。更大的范围为保证页面流畅而做了限制。
• 不接受小数和负数。只能输入1以上的整数。

如何使用结果

结果是合数时,可以借助质因数分解求约数个数(各指数加1后相乘)、最大公约数和最小公倍数等。例如360 = 2³×3²×5,约数个数为 (3+1)(2+1)(1+1) = 24个。 在编程中,哈希表长度或简单随机数发生器的模数常选素数,因为余数的规律不容易重复。 在密码学中,RSA依赖的是“两个大素数相乘容易、从乘积分解回去很难”这一性质,但实际使用的素数有几百位,远超本工具的范围,所以不能用本工具生成密钥。

常见问题

相关工具

• 进制转换器
• 幻方生成器
• 随机数生成器