[转]因数的分解

来源：百度文库编辑：神马文学网时间：2024/04/29 15:54:57

因数的分解来源：数学学习作者：日期：2005-4-9 22:38:14
数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:
设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以2,3,7,8结尾的.
URL http://hahz.com/gb/sxdt/054922432593280.shtml

[转]因数的分解影响丝印质量的因数要辞职得考虑的五大因数同级别分解的一点思考（初稿）（转）能力与能力的分解一只股票走势的分解改进java字符串分解的方法结婚的WBS(工作分解结构) 一题多解数的组成与分解纸面分解任务的一个wap实例一题多解数的组成与分解[20091019] 结婚的WBS(工作分解结构)(2) 结婚的WBS(工作分解结构)汪 4-6分解式的应用结婚的WBS(工作分解结构)2 手套的钩织步骤简要分解结婚的WBS(工作分解结构)3 高清晰的枪械分解图结婚的WBS(工作分解结构) (ancdefgh) 套的钩织步骤简要分解 4-6分解式的深化分析一题多解数的组成与分解kk 手套的钩织步骤简要分解同级别分解的一点思考