质数计算器

质数计算器 - 求和、计数与查找质数

🔢 计算质数之和、查找区间内的质数、判断一个数是否为质数，并求第 n 个质数。 使用快速的埃拉托色尼筛法并带可视化。

什么是质数？

质数是大于 1 的自然数，不能表示为两个更小自然数的乘积。 换句话说，它恰好有两个因数：1 和它本身。

前 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 - 试除法：

• 检查 n 是否能被 2 到 √n 之间的任意整数整除
• 如果能整除，则为合数（非质数）
• 如果不能整除，则为质数

示例：17 是质数吗？

• √17 ≈ 4.12，因此检查 2、3、4
• 17 ÷ 2 = 8.5（不能整除）
• 17 ÷ 3 = 5.67（不能整除）
• 17 ÷ 4 = 4.25（不能整除）
• 结果：17 是质数！

埃拉托色尼筛法

用于找出所有不大于 n 的质数的经典算法：

• 步骤 1：列出 2 到 n 的所有整数
• 步骤 2：标记 2 为质数，划去所有 2 的倍数
• 步骤 3：找到下一个未被划去的数（3），标记为质数
• 步骤 4：划去该质数的所有倍数
• 步骤 5：重复直到 √n
• 结果：未被划去的数都是质数

质数求和

前 n 个质数的和：

• 前 10 个：2+3+5+7+11+13+17+19+23+29 = 129
• 前 100 个：和 = 24,133
• 前 1000 个：和 = 3,682,913

不大于 n 的质数之和：

• 到 10：2+3+5+7 = 17
• 到 100：和 = 1,060
• 到 1000：和 = 76,127

素数定理

小于 n 的质数个数约为 n/ln(n)：

• 到 100：~25 个（实际：25）
• 到 1,000：~145 个（实际：168）
• 到 10,000：~1,086 个（实际：1,229）
• 到 100,000：~8,686 个（实际：9,592）

质数类型

孪生质数：相差 2 的质数对

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

梅森质数：形如 2ᵖ - 1（p 为质数）

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• 已知最大质数为梅森型（约 2480 万位！）

索菲·热尔曼质数：质数 p 且 2p+1 也为质数

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

费马质数：形如 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• 已知费马质数只有 5 个

质数的应用

密码学（RSA）：

• 基于大整数因式分解的困难性
• 使用两个大质数（数百位）
• 保护网银、邮件、网站等

哈希表：

• 质数大小的哈希表可减少冲突
• 用于数据库与缓存

随机数生成：

• 质数有助于产生更好的伪随机序列
• 用于模拟与游戏

有趣的质数事实

• 无限性：欧几里得（约公元前 300 年）证明质数无限
• 间隔：可以任意大（连续很长一段没有质数）
• 哥德巴赫猜想：每个大于 2 的偶数都是两个质数之和（未证明！）
• 黎曼猜想：关于质数分布的著名难题
• 质数间隔：相邻质数差通常会变大
• 概率：随机 n 为质数的概率约为 1/ln(n)

质数记录

• 已知最大质数：2^82,589,933 - 1（2018 年发现，24,862,048 位）
• 最大孪生质数：2,996,863,034,895 × 2^1,290,000 ± 1
• 计算：GIMPS（Great Internet Mersenne Prime Search）分布式项目

常见误区

• 1 不是质数：按现代定义（必须恰好有 2 个因数）
• 并非所有奇数都是质数：9, 15, 21, 25... 是合数
• 生成所有质数的公式：不存在简单公式能生成全部质数
• 质数有规律：没有可预测的固定模式（看起来像随机）

💡 小提示：判断一个大数是否为质数，只需测试到它的平方根即可！ 例如判断 997 是否为质数，只需测试到 √997 ≈ 31.6，也就是 2、3、5、7、11、13、17、19、23、29、31。 如果这些都不能整除 997，那么 997 就是质数！另外，除 2 和 3 外，所有质数都可写成 6k±1 的形式，能进一步加速搜索。