[BOJ_11653] 소인수 분해

설명

---

입력이 들어오면 그 숫자를 소인수 분해하면 된다.

 

출력 형태를 보니 재귀로 처리하면 쉽게 처리 할 수 있을 것으로 판단하여 재귀 형태로 짰고 모든 수를 탐색하여 소수를 찾아서 나눠도 되지만 제곱근 내에서만 탐색하면 해당 숫자 내부의 소수를 모두 찾아서 판단할 수 있어서 아래와 같이 코드를 짰다. 그리고, 마지막에 출력 추가 부분은 다 나누고 마지막에 남는 소수를 찾기 위해서 추가하였다.

 

마지막에 남은 수가 소수일 경우  제곱근으로 반복문 돌리는 방식은 자기 자신이 소수일때는 자기 자신의 수 내부에 존재하는 소수를 찾지 못하고 (소수는 1 아니면 자기 자신으로만 나누어진다.) 마지막에 남은 소수 바로 자신을 출력하면 된다.

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_11653 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        if(N == 1){
            return;
        }
        int a = Make(N);
        System.out.println(a);
    }

    private static int Make(int n) {
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                System.out.println(i);
                n = Make(n/i);
                break;
            }
        }
        return n;
    }
}

11653번: 소인수분해