质因数信息和计算

质因数信息和计算


发布日期: 2016-10-24 更新日期: 2017-01-12 编辑:xuzhiping 浏览次数: 4659

标签:

摘要: 基本信息 即是一个数的约数,并且是质数,比方8=2×2×2,2即是8的质因数。12=2×2×3,2和3即是12的质因数。把一个式子以12=2×2×3的方式表明,叫做分化质因数。16=2×2×2×2,2即是16的质因数,把一个合数写成几个质数相乘的方式表明,这也...

基本信息

即是一个数的约数,并且是质数,比方8=2×2×2,2即是8的质因数。12=2×2×3,2和3即是12的质因数。把一个式子以12=2×2×3的方式表明,叫做分化质因数。16=2×2×2×2,2即是16的质因数,把一个合数写成几个质数相乘的方式表明,这也是分化质因数。

分化质因数的办法是先用一个合数的最小质因数去掉这个合数,得出的数如果一个质数,就写成这个合数相乘方式;如果一个合数就持续按原来的办法,直至终究是一个质数 。

分化质因数的有两种表明办法,除了大家最常用知道的“短除分化法”之外,还有一种办法即是“塔形分化法”。

分化质因数对处理一些自然数和乘积的疑问有很大的协助,一起又为求最大公约数和最小公倍数做了主要的铺垫。

Pollard Rho因数分化

1975年,John M. Pollard提出了第二种因数分化的办法,Pollard Rho迅速因数分化。该算法时间复杂度为O(n^(1/4))。

计算方法

短除法

求最大公因数的一种办法,也可用来求最小公倍数。

求几个数最大公因数的办法,开始时用调查比较的办法,即:先把每个数的因数找出来,然后再找出公因数,终究在公因数中找出最大公因数。

例如:求12与18的最大公因数。

12的因数有:1、2、3、4、6、12 、16、18。

18的因数有:1、2、3、6、9、18、24。

12与18的公因数有:1、2、3、6。

12与18的最大公因数是6。

这种办法对求两个以上数的最大公因数,特别是数目较大的数,显然是不便利的。于是又选用了给每个数别离分化质因数的办法。

12=2×2×3

18=2×3×3

12与18都能够分红几种方式不一样的乘积,但分红质因数连乘积就只有以上一种,并且不能再分化了。所分出的质因数无疑都能整除原数,因而这些质因数也都是原数的约数。从分化的成果看,12与18都有公约数2和3,而它们的乘积2×3=6,即是 12与18的最大公约数。

选用分化质因数的办法,也是选用短除的方式,只不过是别离短除,然后再找公约数和最大公约数。如果把这两个数合在一起短除,则更简单找出公约数和最大公约数。

从短除中不难看出,12与18都有公约数2和3,它们的乘积2×3=6即是12与18的最大公约数。与前边别离分化质因数相比较,能够发现:不仅成果相同,并且短除法竖式左边即是这两个数的公共质因数,而两个数的最大公约数,即是这两个数的公共质因数的连乘积。

实践使用中,是把需求核算的两个或多个数放置在一起,进行短除。

在核算多个数的最小公倍数时,对其间恣意两个数存在的约数都要算出,其它无此约数的数则原样落下。终究把一切约数和终究剩余无法约分的数连乘即得到最小公倍数。

只富含1个质因数的数一定是亏数。

关注公众号
获取免费资源

随机推荐


Copyright © Since 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org