当前位置: 代码迷 >> J2SE >> 这个实现分解质因数的代码如何理解
  详细解决方案

这个实现分解质因数的代码如何理解

热度:96   发布时间:2016-04-23 20:01:07.0
这个实现分解质因数的代码怎么理解
import java.util.Scanner;

public class Fenjiezhiyinshu {

public static void main(String[] args){ 
Scanner scan=new Scanner(System.in);
String str=scan.nextLine();
String[] strs=str.split(" ");

int n=Integer.parseInt(strs[0]);
int m=Integer.parseInt(strs[1]);

for(int i=n;i<=m;i++){
//调用分解质因数的函数
fen_jie_zhi_yin_shu(i);
}
scan.close();
}

public static void fen_jie_zhi_yin_shu(int x){
int sushu=2;
int n=x;
int first=1;
while(sushu<=n){
if(x%sushu != 0){
sushu++;
}else {
x/=sushu;
if(first==1){
System.out.print(n+"="+sushu);
first++;
}else{
System.out.print("*"+sushu);
}
}
}
System.out.println();
}
}

fen_jie_zhi_yin_shu方法中的算法流程看懂了,但是要怎么理解呢?为什么那样就可以分解出来。
------解决思路----------------------
首先理解分解质因数的原理:  将一个数分解成素数相乘的积  
所谓的素数(质数):分解质因数后是1*(值本身)
你可以添加断点调试一下:
如:60=2*2*3*5
------解决思路----------------------
// 对3472求质因数,改进前需要3477运算,改进后需要35次
public static void fen_jie_zhi_yin_shu(int x) {
int num = 0;// 用于统计运行次数,与算法实现没什么关联
int sushu = 2;// 用于试除的数
int n = x;// 保留当前将被分解的数值
int first = 1;// 用于控制显示,和算法实现关联不大
while (sushu <= n) {
// if(x%sushu != 0){//性能改进
if (n % sushu != 0) {
// 当前的sushu不是n的因数,增加1,试验下一个数
// 因为是从最小的素数开始试除的,如果sushu不是素数,一定会走这个分支
sushu++;
} else {
// // 不把这段代码移到上面来,显示会有问题
// 输出得到的一个因数,因为循环是从最小的素数开始试除的,所以,当前的
// sushu的值一定是素数
if (first == 1) {
System.out.print(n + "=" + sushu);
first++;
} else {
System.out.print("*" + sushu);
}
// x/=sushu;//性能改进
// 得到当前n的另一个因数
n /= sushu;
// if (first == 1) {
// System.out.print(n + "=" + sushu);
// first++;
// } else {
// System.out.print("*" + sushu);
// }
}
//检查算法效率用的,和算法关系不大
num++;
}
//以下是显示用的,和算法关系不大
System.out.println();
System.out.println("num=" + num);
}

我试验了一下,做了点改动,写了一下注释,不清楚达到你的要求没有。
  相关解决方案