[Java] 백준 #11653 (기본 수학2)

📍 출처

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

📝 문제

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

⌨️ 입력

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

🖨 출력

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

⌨️ 예제 입력 1

72

🖨 예제 출력 1

2
2
2
3
3

⌨️ 예제 입력 2

3

🖨 예제 출력 2

3

📚 내가 제출한 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();

		for(int i = 2; i <= Math.sqrt(num) ; i++){
			while(num % i == 0){
				System.out.println(i);
				num /= i;
			}
		}

		if(num != 1){
			System.out.print(num);
		}
	}
}

✏️ 내가 제출한 코드에 대한 설명

소인수분해를 하는 문제로 소인수분해란 소수로 인수를 분해하는 것이다. 예를 들면 18이라는 수가 주어졌을 때 소수인 2, 3, 3으로 분해하는 것이다.

문제를 해결 한 순서로는 우선 소인수분해 할 값을 입력받는다. 그리고 가장 작은 소수인 2부터 시작하여 받은 값의 제곱근까지 반복문을 돌려준다. 제곱근까지 한 이유는 14일차에도 설명했듯이 어떤 N이 두 개이상 곱셈(인수)으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같다는 것이다.

반복문 안에 다시 반복문을 넣어 주어진 수와 i 모듈러가 나누어 떨어진다면 num의 인수기 때문에 i를 출력해주며 num을 i로 나누어준다.

이 과정을 거치면 2개의 경우의 수가 생긴다. num /= i 를 통해 num이 1까지 나누어지는 경우와 제곱근보다 큰 소수가 남는 경우다. 따라서 마지막에 num이 1이 아니라면 마지막 남은 소수를 출력해주었다.