这个计算器能做什么
这是一款三合一的质数工具。它可以:(1)查询第 n 个质数,即 \(P_{\text{n}} = p_{\text{n}}\);(2)判断某个整数是否为质数,并给出它在质数序列中的位置;(3)一键列出前 N 个质数。最前面的几个质数是 2、3、5、7、11、13、17……所谓质数(素数),是指大于 1、且除了 1 和它本身之外没有其他正因数的整数。
使用方法
先选择一种模式。在第 n 个质数模式下,输入从 1 开始计数的位置 \(n\)(例如 100),计算器会返回 \(\text{Prime}[100] = 541\)。在质数判断模式下,输入任意整数(例如 97),它会告诉你这个数是否为质数;如果是,还会给出它在质数序列中的序号 \(n\)。在列出前 N 个质数模式下,输入想要的质数个数,即可得到用逗号分隔的完整列表,以及其中最大的质数 \(\text{Prime}[\text{N}]\)。
公式原理
质数判断采用试除法:当 2 到 \(\sqrt{p}\) 之间不存在任何整数因数时,数字 \(p\) 即为质数。
$$\text{N} \text{ is prime} \iff \text{N} \ge 2 \;\wedge\; \nexists\, d \in \left[2,\;\sqrt{\text{N}}\,\right]: d \mid \text{N}$$在单独处理 2 之后,我们只需检验奇数因数 \(d\),并且只要满足 \(d \cdot d \le p\) 即可,这样计算又快、又能避免浮点误差。要找出第 n 个质数,就依次扫描候选数 2、3、4……,每遇到一个质数就计数一次,直到计数达到 \(n\)。质数 \(m\) 的序号等于 \(\pi(m)\),也就是小于或等于 \(m\) 的质数个数。
实例演算
以 97 为例。它是奇数,于是我们依次尝试 \(d = 3, 5, 7, 9\)(因为 \(9^2 = 81 \le 97\),而 \(11^2 = 121 > 97\))。这些数都不能整除 97,所以 97 是质数。再数一数不超过 97 的质数:2、3、5……97,共 25 个,因此 97 是第 25 个质数:$$\text{primeIndex} = 25$$
质数参考:前25个质数与索引检查点
索引 \(n\) 表示质数在递增质数序列中的位置,因此 \(p_n\) 是第 \(n\) 个质数。下表列出了前25个质数。
| n | pn | n | pn | n | pn | n | pn | n | pn |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
索引检查点
| 表达式 | 数值 | 含义 |
|---|---|---|
| \(p_{100}\) | 541 | 第100个质数是541 |
| \(p_{168}\) | 997 | 第168个质数是997,是小于1000的最大质数 |
| \(p_{1000}\) | 7919 | 第1000个质数是7919 |
| \(\pi(10)\) | 4 | 不超过10的质数:2、3、5、7 |
| \(\pi(100)\) | 25 | 不超过100的质数有25个(最后一个是97) |
| \(\pi(1000)\) | 168 | 不超过1000的质数有168个 |
| \(\pi(10000)\) | 1229 | 不超过10,000的质数有1229个 |
请注意两种记号之间的联系:若 \(p\) 为质数,则当且仅当 \(p = p_n\) 时 \(\pi(p) = n\)。例如,\(\pi(997) = 168\) 且 \(p_{168} = 997\)。
质数术语解释
- 质数: 大于1的整数,且其仅有的正因数是1和它自身(例如2、3、5、7、11)。
- 合数: 大于1的整数,且至少有一个除1和它自身以外的因数(例如4、6、9、15)。
- 1很特殊: 数字1既不是质数也不是合数。它只有一个正因数,即它自身。
- 2是唯一的偶质数: 其他所有偶数都能被2整除,因此都是合数。
- 质数索引(位置)n: 质数在有序质数列表中的排名。2的索引是1,3的索引是2,5的索引是3,依此类推,因此 \(p_n\) 表示第 \(n\) 个质数。
- 质数计数函数 \(\pi(x)\): 小于或等于 \(x\) 的质数个数。例如 \(\pi(10) = 4\),\(\pi(100) = 25\)。
- 试除法: 一种素性检验方法,尝试用从2到 \(\sqrt{p}\) 的每个整数 \(d\) 去除 \(p\)。若没有任何数能整除 \(p\),则 \(p\) 是质数。只需检查到 \(\sqrt{p}\) 就足够了,因为任一因数对中至少有一个数不超过 \(\sqrt{p}\)。
- 互质: 若两个整数的最大公约数为1,则它们互质(相对质数)。两个不同的质数总是互质的,但互质的数不一定是质数(8和15互质)。
- 孪生质数: 相差2的一对质数,例如 (3, 5)、(11, 13)、(17, 19)、(29, 31) 和 (41, 43)。
常见问题
1 是质数吗?不是。按照定义,质数必须大于 1,所以 1 既不是质数,也不是合数。
唯一的偶质数是哪个?2 是唯一的偶质数;其他所有偶数都能被 2 整除。
第 100 个质数是多少?\(\text{Prime}[100] = 541\)。其他参考值:\(\text{Prime}[10] = 29\)、\(\text{Prime}[25] = 97\)、\(\text{Prime}[50] = 229\)、\(\text{Prime}[223] = 1409\)。