齐心教育

 找回密码
 注册

QQ登录

只需一步,快速开始

查看: 3156|回复: 0

分解质因数的方法

[复制链接]
发表于 2013-4-25 12:56:06 | 显示全部楼层 |阅读模式
  每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。 分解质因数只针对合数。

  原理

  任何一个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数,叫做这个合数的分解质因数。

  分解质因数只针对合数。

  方法

  举个简单例子,12的分解质因数可以有以下几种:12=2x2x3=4x3=1x12=2x6,其中1,2,3,4,6,12都可以说是12的因数,即相乘的几个数等于一个自然数,那么这几个数就是这个自然数的因数。2,3,4中,2和3是质数,就是质因数,4不是质数。那么什么是质数呢?就是不能再拆分为除了1和它本身之外的因数的数,如2,3,5,7,11,13,17,19,23,29等等,质数没有什么特定的规律,不存在最大的质数。

  求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式的叫短除法,和除法的性质差不多,还可以用来求多个个数的公因式:

  如24

  2┖24(是短除法的符号)

  2┖12

  2┖6

  3——3是质数,结束

  得出24=2×2×2×3=2^3×3(m^n=m的n次方)

  再如105

  3┖105

  5┖35

  ----7——7是质数,结束

  得出105=3×5×7

  证明,不存在最大的质数:

  使用反证法:

  假设存在最大的质数为N,则所有的质数序列为:N1,N2,N3……N

  设M=(N1×N2×N3×N4×……N)+1,

  可以证明M不能被任何质数整除,得出M是也是一个质数。

  而M>N,与假设矛盾,故可证明不存在最大的质数。

  Pollard Rho快速因数分解

  1975年,John M. Pollard提出了第二种因数分解的方法。该算法时间复杂度为O(n^(1/4))。详见参考资料[1]。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则


关于我们|电话:010-58674462|手机版|北京朝阳区劲松富顿中心C座501室|Archiver|( 京ICP备16067677号 )|齐心教育版权所有  

GMT+8, 2020-2-20 09:58 , Processed in 0.071036 second(s), 20 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表