主数检查器
检查一个数是否是素数,并找到它的因数. 使用这个免费的素数检查器即时测试任何数,并找到所有素数因数. 无需注册.
一个素数是什么?
一个素数是一个大于1的自然数,它有两个完全不同的因子: 1和它自己.第一个素数是: 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...
关于素数的主要事实:
- 2是唯一一个偶数的素数.任何其他偶数都可以被2除,所以它有两个以上的因子.
- 1 不是素数通过现代的惯例. 排除1保留了素因数分解的独特性 (算法的基本定理).
- 素数是无限的欧几里德在公元前300年左右证明了这一点:假设所有素数p1,p2, ..., pn的有限列表.那么数 (p1 x p2 x ... x pn) + 1要么是素数本身,要么是没有素因子的数--矛盾.因此列表是无限的.
- 随着数量变大,质数变得越来越少,永远不要停止在100以下有25个素数,在1000以下有168个,在100万以下有78,498个.
A 复合数是任何比 1 大的正整数,它不是素数--它除了 1 和它自己之外至少有一个因数. 数字 12 是复合数,因为 12 = 2 x 6 = 3 x 4 = 2 x 2 x 3. 每个复合数都有一个独特的素因数分解 (算法的基本定理).
如何检查一个数是否是素数
有几种方法用于初级性测试,从简单的试验划分到先进的概率算法:
试验部门 (基本方法):测试2到√n之间的任何整数是否均 地除除n.如果没有,n是素数.你只需要检查到√n,因为如果n=a x b与a <= b,那么a <= √n.如果没有除数到√n,那么在√n以上也没有.
优化试验划分:检查分于2后,只测试奇数.进一步:检查2,3,然后只测试6k+/-1形式的数 (因为所有素数>3都是这种形式的).这将测试数量比原始试验除法减少约66%.
| 编号 | √n (大约) | 测试除数高达 | 总理? |
|---|---|---|---|
| 97 | 9.85 年 | 2,3,5,7 年 | 是的 (没有均 划分) |
| 91 | 9.54 年 | 2,3,5,7 年 | 没有 (7×13=91) |
| 一百零九 | 31.76 年 | 最多31个 | 是的 (主要) |
| 一百零一 | 31.64 年 | 最多31个 | 没有 (7 x 11 x 13 = 1,001) |
| 七百九十九 | 美国 | 最多89个 | 是的 (第1000个素数) |
对于大数 (数百位数),试验划分在计算上是不可行的.米勒-拉宾初级性测试在密码学中使用) 和AKS首次性测试(决定性多项式时间,2002) 代替.
主因数分解
每个复数都可以写成一个唯一的素数乘法 - - 它的素因数分解.这是由算术基本定理保证的. 为了找到素因数分解,反复除以最小的素因数:
| 编号 | 素因数分解 | 分数树的分解 |
|---|---|---|
| 12 | 22×3 个 | 12 -> 4x3 -> 2x2x3 |
| 60 | 22×3×5 个 | 60 -> 4x15 -> 22x3x5 |
| 一百个 | 22 x 52 个 | 100 - - 4×25 - - 22×52 这样一来, |
| 其他 | 23 x 32 x 5 个 | 360 - - 8x45 - - 23x32x5 的 |
| 1,024人 | 美国 | 所有的素因数都是2 |
| 其他 | 2 x 3 x 5 x 7 x 11 个 | 第一个5个素数的乘积 |
素因数分解是用来找出数的最大公分数 (GCD) 和最小公倍数 (LCM). GCD ((12, 18) = 22 x 3? 没有 - 取共享的素数的最小次数: GCD = 21 x 31 = 6. LCM取最大次数: LCM ((12, 18) = 22 x 32 = 36.
为什么素数很重要:在数学和技术中的应用
素数是算法的"原子" - - 算法的基本定理指出,每一个大于1的正整数要么是素数,要么可以表达为素数的唯一乘积.这种独特性使得素数成为所有数的不可缩小的构建块.
现代互联网安全取决于质数. RSA 加密 (用于 HTTPS,电子邮件加密和数字签名) 通过乘以两个大质数 p 和 q 来生成 n = p x q 生成公钥. 加密和解密密钥是使用模块化算术计算的. 安全性依赖于整数分解问题给定n (一个2048位数,十进制位数为617位),用当前的技术找出p和q是无法计算的.
迪菲 - 赫尔曼密钥交换当你通过HTTPS连接到一个网站时, 素数在实时保护你的数据.
哈希表使用素数大小的数组来最大限度地减少碰撞.当哈希函数将键映射到桶指数时,使用一个素数的桶可以确保更好的分布,因为素数没有可以创建系统碰撞模式的因子.
伪随机数生成器(PRNGs) 在线性对应生成器和其他算法中使用素数模块.这些生成器的周期 (重复前) 通常等于素数模块减去1.
特殊类型的保证金
在无限的素数集合中,某些子集具有特殊的属性或意义:
| 类型 | 定义 | 一些例子 |
|---|---|---|
| 双质数 | 奖金差异为2 | 其他类型: |
| 默森素数 | 2n-1形式的保费 | 3,7,31,127,8,191 年 |
| 费马质数 | 2^(2n) + 1 的形式的奖金 | 3,5,17,257,65,537 年 |
| 索菲·日尔曼素数 | p 和 2p+1 都是素数 | 2,3,5,11,23,29 年 |
| 双边素数 | 前向/后向读取相同的保证金 | 11,101,131,151,181 年 |
| 安全素数 | 素数p,其中 (p-1) / 2也是素数 | 5,7,11,23,47,59 年 |
默森素数(2n - 1) 特别重要,因为它们可以使用高效的卢卡斯-莱默测试来测试初数.GIMPS (Great Internet Mersenne Prime Search) 项目利用全球分布式计算来找到新的默森素数.截至2024年,已知最大的默森素数是2^136,279,841 - 1,拥有超过4100万个小数位.
双质数(二分差的素数对) 假定是无限的 (双素数假设),但这仍然未被证明 - - 数学中最著名的开放问题之一.在2013年,Yitang Zhang证明了较弱的结果,即有无限多个素数对的差异最多为7000万,后来改进为246.
质数的分布
随着数量变大,质数变得不那么频繁,但它们的分布遵循由质数定理描述的统计模式:
在素数定理(由Hadamard和de la Vallée-Poussin在1896年独立证明) 指出,大N的质数数到N的数量,表示π(N),大约为N / ln(N:
| N | 实际情况 | 大约N/ln (N) | 密度 |
|---|---|---|---|
| 一百个 | 25 | 21.7 年 | 四分之一 |
| 一千个 | 一百八十八 | 144.8 年 | 六分之一 |
| 一万 | 一百二十九 | 1,085.7 年 | 八分之一 |
| 一万个 | 9,592 年 | 8,685.9 年 | 十分之一 |
| 一百万 | 七十八498 | 72,382.4 年 | 十三分之一 |
| 十亿万 | 50,847,534 年 | 48,254,942 年 | 20分之一 |
在里曼假设- - 一个千 年奖项问题,奖金100万美元 - - 涉及到素数的精确分布.它猜测里曼子函数的所有非微不足道的零都具有实数1/2.这与素数分布的"随机性"有关 - - 假设预测了素数间隙的最佳规律性.
人们常问的问题
1 是一个素数吗?
没有.根据现代数学惯例,1既不是素数也不是复合数.从素数中排除1保留了素因数分解的独特性 (算法的基本定理) - 如果1是素数,每个数都会有无限多个因数分解 (例如,6=2x3=1x2x3=1x1x2x3=...).在历史上,一些数学家确实认为1是素数,但现代定义排除了它.
什么是已知的最大的素数?
截至2024年,已知最大的素数是2^136,279,841 - 1 (默森素数),在2024年10月被发现.它有超过4100万个数字.大互联网默森素数搜索 (GIMPS) 项目使用来自全球志愿者的分布式计算发现了大多数记录的素数.这些巨大的素数没有实际应用 - 它们的搜索纯粹是数学探索.
质数中有没有规律?
素数看起来不规则,但存在模式.所有素数>5以1,3,7或9结尾 (从来不是0,2,4,5,6,8).所有素数>3的形式是6k+/-1.双素数 (不同于2,如11和13) 似乎永远持续 (未被证明的双素数猜想).素数定理描述了近N的素数的统计密度大约为1/lnN.
2 是一个素数吗?
是的,2是素数--它是唯一一个偶数的素数. 2有两个因数 (1和2),满足定义. 其他任何偶数都可以被2除,因此它是复合的. 2的素数是一个特殊的情况,通常需要在算法和证明中单独处理.
如何在加密中使用首要性?
RSA加密生成一个密钥对: (1) 选择两个大质数 p 和 q (每个为 1024+ 位), (2) 计算 n = pxq, (3) 使用模块化算法推导加密密钥 e 和解密密钥 d. 任何人都可以使用 n 和 e (公钥) 进行加密,但只有 p 和 q (或 d) 的持有者才能解密. 安全性依赖于将 n 归化为 pxq 的计算难度.
如何最快地检查一个数是否是素数?
对于小数 (高达~10^12):优化试验划分,使用6k+/-1模式仅检查到√n.对于中等数:用少数证人进行米勒-拉宾初数测试是概率性的,但极快.对于非常大的数 (加密大小,1000个以上的数字):使用许多随机证人进行米勒-拉宾等概率测试,或确定性证明的AKS测试.
什么是质量差?
一个素数间隙是两个连续的素数之间的差异.最小的素数间隙是1 (在2和3之间),所有其他连续的素数间隙至少是2 (因为一个必须是奇数).间隙平均增长缓慢:在N附近,素数之间的平均间隙是ln(N).存在异常大的素数间隙 - 连续的复合数有任意长的序列 (n!+2,n!+3,...,n!+n都是任何n的复合数).
100 的素因数是多少?
100 = 2 x 50 = 2 x 2 x 25 = 2 x 2 x 5 x 5 = 22 x 52. 100 的素因数是 2 和 5. 这种因数分解解释了为什么 100 均 地除以 1, 2, 4, 5, 10, 20, 25, 50, 和 100 - 每个除数对应于 20 1 2 和 50 1 2 的组合.
戈德巴赫的猜想是什么?
戈德巴赫推测 (1742) 指出,每一个大于2的偶整数都可以用两个素数的和来表示.例如: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83.它已经被计算验证到4x10^18,但仍然未被证明.它是数论中最古老和最着名的未解决的问题之一.
有多少个素数?
有无限多的素数 - - 欧几里德在公元前300年左右证明了这一点. 通过矛盾的证明:如果素数是有限的,它们的乘积加1要么是素数,要么有一个素因数不在所谓的完整列表中,这是一个矛盾. 虽然素数在更大的数量上变得不那么密集,但它们永远不会停止. 确切地说,在100万以下有78,498个素数,在100万以下有5,761,455个素数.
数学中的质数和未解决的问题
素数是数学中最美丽,最 固的未解难题的核心. 了解这些未解难题, 揭示了我们对素数的了解 -- 尽管经过了几个世纪的努力, 还有多少问题仍然是神秘的.
里曼假设 (1859):里曼子函数 ζ ((s) = Σ ((1/ns) 通过其零连接到素数的分布.假设说所有非微不足道的零都位于关键直线 Re ((s) = 1/2.如果真实,它将提供最准确的描述,如何分配素数.已计算过10万亿个零,所有都位于关键直线上 - - 但没有证据.这是一个千 年奖问题,由克莱数学研究所授予100万美元的奖金.
双质量假设:是否有无限多的素数对 (p,p+2) - - 如 (11,13), (17,19), (41,43), (101,103)? 猜测说是的,但它仍然未被证明. 在2013年,Yitang Zhang的突破证明有无限多的素数对,差距最多为7000万 - - 这是有史以来第一个有限的边界. 多数数学项目随后将这个边界减少到246,这意味着我们知道有无限多的素数对,差距<=246. 2的差距仍然未被证明.
戈德巴赫的推测 (1742):每个偶数大于2的整数都是两个素数的和. 通过计算验证到4x10^18. 迄今为止尝试的每个偶数都满足它 - 通常以多种方式 (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). 然而,没有证据涵盖所有偶数. "弱戈德巴赫推测" (每个奇数>=7是三个素数的和) 于2013年被哈拉尔德·赫尔夫戈特证明.
默森素数和完整数:默森素数是2n-1 (n本身必须是素数) 的形式之一.前几种是:3,7,31,127,8,191.截至2024年,只有52个已知.默森素数与完整数相连:每个默森素数通过公式2^(p-1) x (2^p - 1) 生成一个偶数完整数.数字28 = 4 x 7 (使用默森素数7) 和496 = 16 x 31 (使用默森素数 31) 是完整数.是否存在无限多个默森素数?未知.
ABC假设及其含义:ABC推测 (于1985年提出) 是关于三个数 a + b = c 的素因子的深度关系.如果证明,它将暗示费马的最后定理和其他许多结果是简单的结果.在2012年,Shinichi Mochizuki发表了使用他的跨宇宙Teichmüller理论的证明 - 但证明是如此新 和复杂,以至于数学界已经讨论了它的有效性十多年,一些数学家接受它,而其他人发现了一个差距.
素数仍然是数学中最大的 团:简单的定义 (一个有两个因子的数),但它们的分布足够复杂,足以解决几个世纪以来最伟大的数学头脑所面临的开放问题.每一个新的素数记录被发现,每一个推测的计算验证达到一个新的极限,每一个部分证明都提高了我们的理解 - - 同时提醒我们还有多么多需要发现.