每日算法（5）——正整數分解質因數

1、分解質因數介紹

每個合數都可以寫成幾個質數相乘的形式，其中每個質數都是這個合數的因數，叫做這個合數的分解質因數。

參考百度。

2、算法思路

先判斷數num是否為合數，如果是，選擇最小的質數k=2，進行分解質因數的過程：

（1）如果k小等于num，程式繼續執行；

（2）如果num能被k整除，說明k是num的一個因數，并用num除以k的商作為新的正整數num，重複執行第一步；否則用k+1作為k的值，重複執行第一步。

3、具體代碼

package com.peter.algorithm.other;

import org.junit.Test;
import java.util.ArrayList;

public class DecomposePrimeNumber {
    @Test
    public void test() {
        ArrayList<Integer> compositeNumberList = new ArrayList<>();
        ArrayList<Integer> primeNumberList = new ArrayList<>();
        for (int i = ; i < ; i++) {
            if (isCompositeNumber(i)) {
                compositeNumberList.add(i);
                System.out.println(decomposePrimeNumber(i));
            } else {
                primeNumberList.add(i);
            }
        }
        System.out.println(compositeNumberList);
        System.out.println(primeNumberList);
    }

    public static String decomposePrimeNumber(int num) {
        if (num <  || num > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("out of range!");
        }
        if (!isCompositeNumber(num)) {
            return num + " is not a composite number!";
        }
        StringBuffer stringBuffer = new StringBuffer(num + "=");
        int begin = ;
        while (num >= begin) {
            if (num % begin == ) {
                stringBuffer.append(begin + "*");
                num /= begin;
            } else {
                begin++;
            }
        }
        return stringBuffer.toString().substring(, stringBuffer.length() - );
    }
    //判斷一個數是否為合數
    private static boolean isCompositeNumber(int num) {
        if (num <  || num > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("out of range!");
        }
        int begin = ;
        int sum = ;
        while (num >= begin) {
            if (num % begin == ) {
                num /= begin;
                sum++;
            } else {
                begin++;
            }
        }
        return sum >  ? true : false;
    }
}
           

4、2至99之間的合數分解質因數

類别	具體整數
合數	4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99
素數	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

合數	分解質因數
4	2*2
6	2*3
8	2*2*2
9	3*3
10	2*5
12	2*2*3
14	2*7
15	3*5
16	2*2*2*2
18	2*3*3
20	2*2*5
21	3*7
22	2*11
24	2*2*2*3
25	5*5
26	2*13
27	3*3*3
28	2*2*7
30	2*3*5
32	2*2*2*2*2
33	3*11
34	2*17
35	5*7
36	2*2*3*3
38	2*19
39	3*13
40	2*2*2*5
42	2*3*7
44	2*2*11
45	3*3*5
46	2*23
48	2*2*2*2*3
49	7*7
50	2*5*5
51	3*17
52	2*2*13
54	2*3*3*3
55	5*11
56	2*2*2*7
57	3*19
58	2*29
60	2*2*3*5
62	2*31
63	3*3*7
64	2*2*2*2*2*2
65	5*13
66	2*3*11
68	2*2*17
69	3*23
70	2*5*7
72	2*2*2*3*3
74	2*37
75	3*5*5
76	2*2*19
77	7*11
78	2*3*13
80	2*2*2*2*5
81	3*3*3*3
82	2*41
84	2*2*3*7
85	5*17
86	2*43
87	3*29
88	2*2*2*11
90	2*3*3*5
91	7*13
92	2*2*23
93	3*31
94	2*47
95	5*19
96	2*2*2*2*2*3
98	2*7*7
99	3*3*11