每个合数都可以写成几个质数相乘的形式,这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。
定义
质因数(或
质因子)在
数论里是指能整除给定正
整数的
质数。
两个没有共同质因子的正整数称为互质。因
为1没有质因子,1与任何正整数(包括1本身)都是互质。
正整数的因数分解可将正整数表示为一连串的质因子相乘,质因子如重复可以指数表示。根据算术基本定理,任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。
例子
就是一个数的
约数,并且是
质数,比如8=2×2×2,2就是8的质因数。12=2×2×3,2和3就是12的质因数。把一个式子以12=2×2×3的形式表示,叫做
分解质因数。16=2×2×2×2,2就是16的质因数,
把一个合数写成几个质数相乘的形式表示,这也是分解质因数。
[1]
分解质因数的方法是先用一个合数的最小质因数去除这个合数,得出的数若是一个质数,就写成这个合数相乘形式;若是一个合数就继续按原来的方法,直至最后是一个质数 。
分解质因数的有两种表示方法,除了大家最常用知道的“短除分解法”之外,还有一种方法就是“塔形分解法”。
计算方法
短除法
求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式的叫短除法,和除法的性质差不多,还可以用来求多个个数的公因式:
求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数。
例如:求12与18的最大公因数。
12的因数有:1、2、3、4、6、12。
18的因数有:1、2、3、6、9、18。
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的最大公约数。与前边分别分解质因数相比较,可以发现:不仅结果相同,而且
短除法竖式左边就是这两个数的公共质因数,而两个数的最大公约数,就是这两个数的公共质因数的连乘积。
实际应用中,是把需要计算的两个或多个数放置在一起,进行短除。
在计算多个数的最小公倍数时,对其中任意两个数存在的约数都要算出,其它无此约数的数则原样落下。最后把所有约数和最终剩下无法
约分的数连乘即得到最小公倍数。
(短除法详解:
短除符号就是除号倒过来。短除就是在除法中写
除数的地方写两个数共有的
质因数,然后落下两个数被公有质因数整除的商,之后再除,以此类推,直到结果
互质为止(两个数互质)。
而在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是
互质关系。
求最大公因数遍乘一边,求最小公倍数遍乘一圈。
(
公约数:亦称“公
因数”。是几个整数同时均能整除的整数。如果一个整数同时是几个整数的约数,称这个整数为它们的“公约数”;公约数中最大的称为最大公约数。)
在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。
求最大公约数遍乘左边所有数公共的因数,求最小公倍数遍乘一圈。这种方法对求两个以上数的最大公因数,特别是数目较大的数,显然是不方便的。于是又采用了给每个数分别
分解质因数的方法
)
Pollard Rho因数分解
1975年,John M. Pollard提出了第二种因数分解的方法,Pollard Rho快速因数分解。该算法时间复杂度为O(n^(1/4))。
分解质因数代码:
将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。
程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成:
(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。
(2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,
重复执行第一步。
(3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。
06 |
printf ( "\nplease input a number:\n" );
|
另一种形式:
02 |
Integer[] decPrime( int n) {
|
03 |
List<Integer> list = new ArrayList<Integer>();
|
04 |
for ( int i=2;i <= n;i++){
|
10 |
list.add(Integer.valueOf(i));
|
14 |
list.add(Integer.valueOf(n));
|
15 |
return list.toArray( new Integer[list.size()]);
|
另外代码:
。我们用所有正整数试验一下,从2开始进行试除,逐步增加除数的值,去寻找一个可以整除n的数。在Eratosthenes筛法的讨论中,我们知道如果n是一个复合数,那么它就会有一个素数 。算法9.3所示的就是这种方法的伪代码。这个算法有两个偱环路径,外部的和内部的。外部循环求唯一因数,内部循环求一个因数的多个复本。例如, ,外部循环求出因数2和3。内部循环求出2是一个多因数。
01 |
void trial_divisio_fac( int n)
|
上面的代码解释比较清楚。为什么这种方法可以得到素数。
因为我们在内层循环中,已经把当前a的所有倍数都去除了。这跟埃斯托尼算法是一样的。
复杂度 如果 ,这种情况下试除法通常都是很有效的。但是如果用来分解更大的整数,试除法就变得非常低效甚至不可用了。这种算法的复杂度是随着n的增加呈指数级别增长的。
(
试除法是整数分解算法中最简单和最容易理解的算法。
给定一个合数n(这里,n是待分解的整数),试除法看成是用小于等于的每个素数去试除待分解的整数。如果找到一个数能够整除除尽,这个数就是待分解整数的因子。
).
例9.29
运用试除算法求1233的因数。
1233=3^2*137.
参考:http://www.acmerblog.com/integer-factorization-5124.html
相关推荐
c++实现质因数分解,主要是快速,因为分解用普通方法也可以,如何快速分解呢,答案是用筛选法先求出质数,然后分解质数就很快了
首先来看一个最简单的C语言实现质因数分解的列子: #include void main( ) { int data, i = 2; scanf("%d", &data); while(data > 1) { if(data % i == 0) { printf("%d ", i); data /= i; } else i++;...
质因数分解算法例如90=2*3*3*5 java实现
Java实现正整数分解质因数的例子。如果数学好,相信这个代码不会难。在本例子中,输入90,打印出90=2*3*3*5。解题思路和方法:对n分解质因数,需要先找到一个最小的质数k,然后按下述步骤完成: (1)如果这个质数恰...
一个简短的java质因数分解的小程序,算法不是很精巧,但是很容易懂
可以对超过64位最大整数(18446744073709551615,约1845亿亿,20位十进制数)的整数分解质因数。原创的全部源代码共享。 使用了.NET库的“大整数”类。界面为 Win Form 程序使用确定性算法。 做了尽可能多的优化...
计算机算法设计与分析的整数质因数分解问题
根据PallardRho算法,对给定的一个输入,输出的是输入分解而得的素数因子。利用了数学素数分布定理
分解质因数C++的程序算法设计,较为高效的实现办法
c语言大数的因子分解-C语言经典算法:如何较快的分解质因数,排序算法数据结构 最快的排序算法
使用c语言 来求解分解质因数的这样一个常见算法问题
为了实现质因数分解,我们可以编写一个简单的程序。这个程序通常接受一个正整数作为输入,然后通过一系列的计算步骤,找出这个数的所有质因数。这个过程需要用到循环和条件判断等基本的编程结构,是学习和理解编程...
VB 分解质因数 VB 分解质因数 VB 分解质因数
对数字感兴趣的可以来交流一下。我喜欢玩数字游戏,限于脑子算力有限,就学了下c++来帮助自己算数。
主要介绍了Java实现的质因数分解操作,结合实例形式较为详细的分析了Java基于递归算法实现针对整数的质因数分解相关操作技巧,需要的朋友可以参考下
我写的分解质因数算法和排队报数算法。其中排队问题为:若干人站成一个首尾相连的环,从第一个人开始从1到3报数,每次数到3的人站出来,问最后剩下的那个人是原先的第几个人
因数分解(也称为质因子分解):将一个大整数分解它的质因子之乘积的算法。 Pollard Rho算法的基本思路:先判断当前数是否是素数(质数),如果是,则直接返回。如果不是,继续找到当前数的一个因子(可以不是质...
本文实例讲述了Python实现将一个正整数分解质因数的方法。分享给大家供大家参考,具体如下: 遇到一个python编程联系题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。 版本一: 开始,没动脑子就开始...
本文实例讲述了Python实现正整数分解质因数操作。分享给大家供大家参考,具体如下: 遇到一个Python编程练习题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。 #!/usr/bin/env python # -*- coding: ...
如果剩余的整数仍然是复合的,那么它只有很大的因素,并且使用通用技术来分解。迄今为止使用ECM发现的最大因素有83位十进制数字,并于2013年9月7日由R. Propper发现。[1]增加测试曲线的数量可以提高找到因子的几率...