主因分数计算器

什么是素因子分解?

素因数分解是将一个复合数分解为其独特的素积木集的过程.一个素数是一个大于1的自然数,只能被1和它自己除,比如2,3,5,7,11,13,17,19,23.复合数是任何大于1的整数, 不是素数-- 意思是它至少有一个除1和它自己之外的因数.

当我们对360这样的数进行素因数分解时,我们将其表达为素数的乘法:360=23x32x5. 这个表示对于每一个整数都是独一无二的 -数学的基本定理它指出,每一个大于1的整数要么是素数本身,要么可以被表示为素数的唯一乘积 (不考虑因数的顺序).

这一概念已被研究了2000多年.其他元素(公元前300年左右) 包含了无限数的证明和基本定理的最早形式,使得素因数分解成为数学中最古老的连续研究的问题之一.

数学的基本定理

数学基本定理是数论的基石.它有两个部分:第一,每一个大于1的整数都可以用质数的乘积表示;第二,这个表示是唯一的 (直到因数的顺序).例如,12=22×3,不管你采取什么方法,你总是会得到正确的那些有正确的指数的质因数.

这种独特性使得素因数分解变得如此强大.没有它,算术运算,如找到GCD和LCM,简化分数,或证明可分割性质将会更加复杂.该定理几乎支 了所有的初级和中间数理论.

一个有趣的结果:如果你想知道一个整数n分成一个整数m你可以比较它们的素因数分解.n划分m如果和只有如果每一个出现的素数的因数分解n也出现在因数分解中.m它们的指数至少同样高.

如何找到素因子:逐步方法

有两种主要的手动因子分解方法:分数树以及重复的分裂.

分数树方法:写出顶部的数字并将其分成任意两个因数.继续分成每个复合因数,直到所有分支以素数结束.对于180:分成4和45 ->分成4成2和2 ->分成45成9和5 ->分成9成3和3.收集所有叶节点: 2 x 2 x 3 x 3 x 5 = 22 x 32 x 5.

重复的除法:把这个数除以最小的素数,然后把分数除以最小的素数,等等. 360: 360 ÷ 2 = 180 -> 180 ÷ 2 = 90 -> 90 ÷ 2 = 45 -> 45 ÷ 3 = 15 -> 15 ÷ 3 = 5 -> 5 是素数. 结果: 23 x 32 x 5.

关键快捷方式:你只需要测试数的平方根为数的素除法数.如果没有一个素除法数直到√n,那么n本身就是一个素.对于n=97,√97~9.85,所以你只需要测试2,3,5,7.因为没有一个素除法数能除法97,它就是一个素.这大大减少了大数的工作.

主因分数参考表

下面是一个参考表,显示常见整数的素因数分解:

分数数的公式:如果n=p1^a x p2^b x p3^c...,那么因子的总数是 (a+1) ((b+1) ((c+1)...对于360=23 x 32 x 51:因子= (3+1) ((2+1) ((1+1) = 4 x 3 x 2 = 24.

素因数分解的应用

最大的共同除法数 (GCD):为了找出 GCD ((48,180),把它们分成因数 - - 48 = 24 x 3,180 = 22 x 32 x 5 - - 然后取出每一个普通素数的最小指数: GCD = 22 x 3 = 12. GCD 用于简化分数: 48/180 = 4/15 (把它们分成12).

最小共同倍数 (LCM):在两个因数分解中,取每个素数的最大指数. LCM ((48,180) = 24 x 32 x 5 = 720. LCM用于加不同分母的分数时 - 你需要一个共同分母,即LCM ((分母1,分母2).

密码学 (RSA):大数分解的难度 - - 特别是两个大素数的乘积 - - 是RSA加密的数学基础.RSA-2048使用的公钥是两个1024位的素数的乘积.用当前的算法来分解它需要比宇宙的年龄更长的时间.这种安全性是HTTPS,电子邮件加密和数字签名的基础.

简化表达式:在代数中,分解多项式与整数分解具有概念上的相似性.就像12 = 4 x 3 = 22 x 3一样,表达式x2 - 9因子为 (x-3) ((x+3).素因数分解思维直接转移到代数操作.

素数及其分布

素数本身是无尽的迷人.前几个素数是2,3,5,7,11,13,17,19,23,29,31,37,41,43,47...随着数量变大,素数变得越来越少,但它们永远不会停止出现.欧几里德在2300多年前用一个非常简单的矛盾证明证明了这一点.

在素数定理(由Hadamard和de la Vallée Poussin在1896年独立证明) 指出,直至n的素数数量大约是n / ln(n.这意味着大约每 ln(n) 个整数中的1个接近n是素数 - - 所以接近100万个,大约14个数中的1个是素数;接近10亿个,大约21个中的1个.

特殊类别的质数包括:双质数(对差异为2:11和13,17和19),默森素数(形式为2^p - 1;截至2024年,已知最大的素数是有超过4100万位数的默森素数),以及索菲·日尔曼素数是否存在无限多的双质数是一个开放的问题 - - 双质量假设.

分因数算法:从试验划分到先进方法

对于小数量 (不到10亿),试验部门我们的计算器使用这种方法, 在几十亿毫秒内处理数量.

对于更大的数,数学家们已经开发出更复杂的算法.费马因子分解法通过将n表示为两个平方的差:n = a2 - b2 = (a+b) ((a-b).波拉德的rho算法(1975) 是一种对具有小因子的数有效的概率方法;它运行在O{n^{1/4)) 时间内,并且在许多现实应用中使用.

已知最强大的通用因子算法是一般数字场 (GNFS)在2009年,GNFS被用于RSA-768 (一个768位RSA挑战号) 的因子,需要相当于2000年的单核CPU时间分布在许多计算机上.RSA-2048被认为在计算上无法与经典计算机进行因子.

量子计算机在理论上可以有效地利用肖尔的算法这就是为什么后量子密码学 - - 开发能够抵御量子攻击的加密技术 - - 是当今的主要研究领域.

教育和竞争性数学中的数因数分解

素因数分解是中学和高中数学中的一个核心技能.它使学生能够简化分数,找到GCD和LCM,使用完整平方和完整立方体,并理解可分割规则.掌握素因数分解也建立了代数的直觉,其中因数分解多项式是一种类似的技能,应用于表达式而不是整数.

在竞争式数学 (AMC,AIME,奥林匹亚) 中,素因数分解问题经常出现. 经典例子:"1,000,000有多少正整数除数?" 由于1,000,000=106= (2 x 5) 6=26 x 56,答案是 (6+1) (((6+1) = 49. 这种类型的问题奖励那些用乘法而不是加法思考的学生.

了解因数分解中的指数也可以解开诸如完整平方 (所有指数均为偶数),完整立方体 (所有指数均可除以3) 和最小的完整平方,

使用素因数分解来简化分数和根数

素因数分解是简化分数的最系统的方法.为了简化 84/126,将两者分解为: 84 = 22 x 3 x 7 和 126 = 2 x 32 x 7. GCD = 2 x 3 x 7 = 42. 所以 84/126 = (84÷42) / 126÷42) = 2/3. 不需要猜测 - 素因数分解直接揭示了 GCD.

对于简化根数,素因数分解同样有效. 简化√180: 180 = 22 x 32 x 5. 素数对来自平方根: √(22 x 32 x 5) = 2 x 3 x √5 = 6√5. 对于立方根: (108) = (22 x 33) = 3 4. 三个组来自立方根.

在竞争式数学中,这些技术经常出现.一个常见的问题类型是:"找到最小的整数n,使360n成为正方形".由于360=23 x 32 x 5,我们需要所有指数均为偶数.目前2的指数是3 (奇数),5的指数是1 (奇数).所以n必须提供至少21 x 51 = 10. 答案:n = 10. 检查:360 x 10 = 3600 = 602.

分数数,完整数和分数和

素因数分解解锁了一个数的除数的完整分析.如果n=p1^a x p2^b x p3^c,那么分数的数是 τ ((n) = (a+1) ((b+1) ((c+1)).分数的和是 σ(n) = ((p1^(a+1)-1) / ((p1-1)) x ((p2^(b+1)-1) / ((p2-1)) x ...

对于 12 = 22 x 3: τ(12) = (2+1) ((1+1) = 6 (除数: 1,2,3,4,6,12). σ(12) = ((23-1) / ((2-1)) x ((32-1) / ((3-1)) = 7 x 4 = 28. A一个完美的数字6 = 2 x 3: σ(6) = 12 = 2x6. 6 是完美的! 28 = 22 x 7: σ(28) = 56 = 2x28. 28 是完美的!

截至2024年,只有51个完整数是已知的,所有都是偶数,所有都是2^{p-1}{2^{p-1}) 的形式,其中2^{p-1}是默森素数.是否存在任何奇数完整数是数学中最古老的开放问题之一 - 没有找到奇数完整数,但没有一个被证明是不可能的.

快速参考:可分割规则

在因数分解之前,可分割规则有助于快速识别因子,而无需进行完全的分割.这些心理快捷方式对于高效的手动因数分解和考试设置至关重要.

记住这些规则使得素因数分解显著更快.对于2520:它是偶数 (÷2),数字和=9 (÷3),以0 (÷5) 结束.从2开始:2520÷2=1260÷2=630÷2=315÷3=105÷3=35÷5=7.所以2520=23 x 32 x 5 x 7 - 一个具有48个除数的高度复合数.