饭后一道题，天天好心情~~

题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。

表示我擅长把简单的事情复杂化，虽然做出结果了，但是算法实在是太坑爹了，我这里不好意思先贴自己的坑爹算法，目测学妹看到了会鄙视我的。。

先看标准答案~简洁无比~

1. package day4;
   
2. 
   
3. import java.util.Scanner;
   
4. 
   
5. public class Test2 {
   
6. 
   
7.         public static void main(String[] args) {
   
8.                 // 解决要分解的数字
   
9.                 System.out.println("请输入要分解的数字(一定要是整数):");
   
10.                 Scanner in = new Scanner(System.in);
    
11.                 int i = in.nextInt();
    
12. 
    
13.                 // 分解方法
    
14.                 int k = 2;
    
15.                 System.out.print(i + "=");
    
16.                 while (i > k) {
    
17.                         if (i % k == 0) {
    
18.                                 System.out.print(k + "*");
    
19.                                 i = i / k;
    
20.                         } else {
    
21.                                 k++;
    
22.                         }
    
23.                 }
    
24.                 System.out.print(i + ";");
    
25.         }
    
26. }
    

复制代码

咳咳，我这里要展示我的坑爹算法了~

看看有没有和我一样这样做的，受上次那道求素数的题的影响，这次我的思路是

（1）算出所有小于 90 的素数
（2）遍历这些素数，然后看看有没有能被90整除的，有的话，把这个整数加入 List
（3）然后用相除的结果递归调用 （1）（2）

1. package day4;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.Iterator;
   
5. import java.util.List;
   
6. 
   
7. /**
   
8. * 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
   
9. *
   
10. * @author yellowbaby
    
11. *
    
12. */
    
13. public class Test {
    
14. 
    
15.         private static List<Integer> integers = new ArrayList<Integer>();
    
16. 
    
17.         public static void main(String[] args) {
    
18. 
    
19.                 decompose(90);
    
20.                
    
21.                 System.out.println(integers);
    
22. 
    
23.         }
    
24. 
    
25.         /**
    
26.          * 利用递归分解整数 i
    
27.          */
    
28.         private static void decompose(int i) {
    
29. 
    
30.                 List<Integer> primes = getPrime(i);
    
31. 
    
32.                 for (Iterator<Integer> it = primes.iterator(); it.hasNext();) {
    
33.                         int current = it.next();
    
34.                         if (i % current == 0) {
    
35.                                 integers.add(current);
    
36.                                 decompose(i / current);
    
37.                                 break;
    
38.                         }
    
39.                 }
    
40.         }
    
41. 
    
42.         /**
    
43.          * 得到小于 i 的所有素数
    
44.          */
    
45.         private static List<Integer> getPrime(int i) {
    
46. 
    
47.                 List<Integer> retVal = new ArrayList<Integer>();// 存放所有的素数
    
48. 
    
49.                 for (int num = 2; num <= i; num++) {
    
50.                         if (isPrime(num)) {
    
51.                                 retVal.add(num);
    
52.                         }
    
53.                 }
    
54.                 return retVal;
    
55.         }
    
56. 
    
57.         /**
    
58.          *
    
59.          * 判断是否是素数，素数的概念：指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数
    
60.          */
    
61.         private static boolean isPrime(int num) {
    
62.                 for (int i = 2; i*i < num; i++) {
    
63.                         if (num % i == 0) {
    
64.                                 return false;
    
65.                         }
    
66.                 }
    
67.                 return true;
    
68.         }
    
69. 
    
70. }
    

复制代码

沙发，顶。

我当时做的时候也是受到前面求素数那道题目的影响，现在看了答案明白了，直接从2一直++去试除即可，如果k不是素数，那么前面的k肯定已经把此时k的质因数除去了，所以i % k == 0的条件就不可能满足，会直接k++。
我的算法里面有求最小素数的方法，有判断是不是素数的方法，确实没想到这些不用判断。{:soso_e134:}

1. class  Test04
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 //参数传入要分解质因数的正整数
   
6.                 resolve(13463634);
   
7.         }
   
8. 
   
9.         //输出
   
10.         public static void resolve(int num)
    
11.         {
    
12.                 //判断是否是正整数
    
13.                 if (num<0)
    
14.                 {
    
15.                         System.out.println("请输入正整数");
    
16.                         return;
    
17.                 }
    
18.                 String result = num+" = ";
    
19.                 int k = 2;
    
20.                 while ((k = minRemNum(num)) != num)
    
21.                 {
    
22.                         result +=k + "*";
    
23.                         num = num/k;
    
24.                         System.out.println(result);
    
25.                 }
    
26.                 System.out.println(result+k);
    
27.         }
    
28. 
    
29.         //获得能整除num的最小素数
    
30.         private static int minRemNum(int num)
    
31.         {
    
32.                 for (int r = 2; r<num+1 ; r++ )
    
33.                 {
    
34.                         if(isRem(r) && num%r==0)
    
35.                                 return r;
    
36.                 }
    
37.                 return 1;
    
38.         }
    
39. 
    
40.         //判断参数是否是素数
    
41.         private static boolean isRem(int r)
    
42.         {
    
43.                 for (int m = 2; m<r ; m++ )
    
44.                 {
    
45.                         if (r%m == 0)
    
46.                                 return false;
    
47.                 }
    
48.                 return true;
    
49.         }
    
50. }
    

复制代码

不错 学习了 c#试试