Java實作 藍橋杯 算法提高 因式分解

算法提高 8-1因式分解

時間限制：10.0s 記憶體限制：256.0MB

送出此題

問題描述

　　設計算法，使用者輸入合數，程式輸出若個素數的乘積。例如，輸入6，輸出23。輸入20，輸出22*5。

樣例

　　與上面的樣例輸入對應的輸出。

　　例：

120=22235

資料規模和約定

　　輸入資料中每一個數在int表示範圍内。

import java.util.ArrayList;
import java.util.Scanner;


public class 因式分解 {
	//擷取2~A之間的所有質數
    public static ArrayList<Integer> getPrimes(int A) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(2);
        for(int i = 3;i <= A;i++) {
            if(judgePrime(i))
                list.add(i);
        }
        return list;
    }
    //判斷數A是否為質數，A為預設大于等于3的數
    public static boolean judgePrime(int A) {
        for(int j = 2;j <= A;j++) {
            if(A % j == 0) {
                return false;
            }
            if(j > A / 2)
                break;
        }
        return true;
    }
    
    public static void printResult(int A) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> tempList = getPrimes(A);
        int len = tempList.size();
        while(A > 1) {
            for(int i = 0;i < len;i++) {
                if(A % tempList.get(i) == 0) {
                    list.add(tempList.get(i));
                    A = A / tempList.get(i);
                    break;
                }
            }
        }
        //輸出結果
        len = list.size();
        for(int i = 0;i < len - 1;i++) 
            System.out.print(list.get(i)+"*");
        System.out.print(list.get(len - 1));
        return;
        
    }
    
    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
        int A = in.nextInt();
printResult(A);
    }

}