[백준 - 11653][Java] 소인수분해

이 포스팅은 자바 8버전으로 풀이가 됐습니다.

 

 

 

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
// 11653번
public class Main {
    public static void main(String[] args)throws IOException {
        try {
            BufferedReader rd = new BufferedReader(new InputStreamReader (System.in));
            
            int num = Integer.parseInt(rd.readLine());
            
            for(int i=2; i<=num;i++) {
                if(num%i==0) {
                    System.out.println(i);
                    num/=i;
                    i--;
                }
            }
        }
        catch(IOException e) {
            System.out.println("error");
        }
    }
}

풀이

소인수 값을 구하는 방법은 다음과 같다.

step 1) 코드 풀이 A(입력 값)%B(i값)를 연산하여 A를 B로 나눈 후 나머지가 0으로 나눠졌을 때 가장 작은 값이다.

step 2) 값을 출력한다.

step 3) 입력 A(num)값에 B(i)로 나눈 값을 A에 다시 저장한다.

ex) 6을 2로 나눌 때 나머지가 3이 나온다.

step 4) 이후 최솟값으로 다시 나눌 수 있는지 확인해야 하므로 i가 증가하지 않도록 -- 연산을 통해서 i-1을 연산한다. 이 연산을 통해서 반복문 for이 돌아갈 때 다시 한번 더 값을 확인할 수 있도록 한다.

 

---

포스팅에 오타나 문제가 있는 경우 댓글 부탁드리겠습니다!

감사합니다. 다음 포스팅 때 뵙겠습니다!

 

 

- 출처 -

https://www.acmicpc.net/problem/11653

11653번: 소인수분해