算法---分解质因数

算法—分解质因数

定义
质因数（或质因子）在数论里是指能整除给定正整数的质数。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。
例子
1没有质因子。
5只有1个质因子，5本身。（5是质数。）
6的质因子是2和3。(6 = 2 × 3)
2、4、8、16等只有1个质因子：2（2是质数，4 = 2，8 = 2，如此类推。）
10有2个质因子：2和5。(10 = 2 × 5)
就是一个数的约数，并且是质数，比如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]

分解质因数代码：
将一个正整数分解质因数。例如：输入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的值,重复执行第一步。

01 #include "stdio.h" 02 #include "conio.h" 03 main() 04 { 05 int n,i; 06 printf("\nplease input a number:\n"); 07 scanf("%d",&n); 08 printf("%d=",n); 09 for(i=2;i<=n;i++) 10 while(n!=i) 11 { 
  
    
  //外部循环求唯一因数，内部循环求一个因数的多个复本 12 if(n%i==0) 13 { 14 printf("%d*",i); 15 n=n/i; 16 } 17 else 18 break; 19 } 20 printf("%d",n); 21 getch(); 22 }

另一种形式： 01 //返回质因数数组  02 Integer[] decPrime(int n) { 03 List<Integer> list = new ArrayList<Integer>(); 04 for (int i=2;i <= n;i++){ 05 while(n != i){ 06 if(n%i != 0){ 07 break;//不能整除肯定不是因数，能够整除在这里一定是质数。因为所有的2，3,5,7  08 //都被除完之后。剩下的因数只能是奇数，且是质数。  09 } 10 list.add(Integer.valueOf(i)); 11 n = n/i; 12 } 13 } 14 list.add(Integer.valueOf(n)); 15 return list.toArray(new Integer[list.size()]); 16 }

类似方法：

// 质因数.cpp : 定义控制台应用程序的入口点。  //  #include "stdafx.h"  #include<cmath>  #include<cstdlib>  #include<iostream>  using namespace std; void Analyse(int n) { //打印出  int i; for(i = 2;i <= sqrt(static_cast<double>(n));i++) { if(n % i == 0) { n = n/i; cout<<i<<"*"; i--; //相当于重复执行 } } cout<<n<<endl; } int _tmain(int argc, _TCHAR* argv[]) { int n; cin>>n; cout<<n<<" = "; Analyse(n); return 0; }

// 质因数.cpp : 定义控制台应用程序的入口点。  #include "stdafx.h"  #include<cmath>  #include<cstdlib>  #include<iostream>  using namespace std; void Analyse(int n) { //首先输出等式左边部分  cout<<n<<" = "; //对n进行质因数分解，应先找到一个最小的质数2  //如果这个质数恰好等于2，则说明分解质因素的过程结束，打印  if(n == 2) { cout<<n<<endl; } //n小于2时，无法进行质因素分解，提示相应信息  else if(n < 2) { cout<<"该数不可以分解质因素"<<endl; } else { //如果n>=k,但n能被k整数，则打印出k的值  for(int i = 2;i <= sqrt(static_cast<double>(n));i++) { if(n % i == 0) { n = n/i; cout<<i<<"*"; //重复执行上一步  i--; } //cout<<n<<endl;  } cout<<n<<endl; } } int _tmain(int argc, _TCHAR* argv[]) { int n; cin>>n; //cout<<n<<endl;  Analyse(n); return 0; }

复杂度如果n<2^10 ，这种情况下试除法通常都是很有效的。但是如果用来分解更大的整数，试除法就变得非常低效甚至不可用了。这种算法的复杂度是随着n的增加呈指数级别增长的。

（

试除法是整数分解算法中最简单和最容易理解的算法。

给定一个合数n（这里，n是待分解的整数），试除法看成是用小于等于的每个素数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是待分解整数的因子。

今天的文章算法---分解质因数分享到此就结束了，感谢您的阅读。

算法---分解质因数

算法—分解质因数

相关推荐