[백준/Java]Q11653

백준 알고리즘 9단계 기본 수학2 11653번 문제입니다.

---

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

[입력]
- 첫째 줄에 정수 N이 주어진다.

 

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

풀이

소인수분해는 1보다 큰 자연수를 소수인 인수들만의 곱으로 나타내는 것이다.

Ex)

• 72 = 2 * 2 * 2 * 3 * 3
• 82 = 2 * 41  
• 125 = 5 * 5 * 5
• 28 = 2 * 2 * 7

소인수분해 결과를 오름차순으로 출력하면 되는 문제이기 때문에 소수 중 가장 작은 수인 2부터 나누기 시작해서 0으로 떨어지지 않는 경우는 증감시키고 0으로 떨어지는 경우는 반복을 해주게 되면 문제를 풀 수 있다.

 

소스

package com.baek.algo.step09;

import java.util.Scanner;

public class Q11653 {

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

		int n = sc.nextInt();

		if(n == 1) {
			System.out.println("");
		} else {
			int num = n;
			int a = 2;

			while(true) {
				if(num <= 1) {
					break;
				} else {
					if(num % a == 0) {
						num = num / a;
		
						System.out.println(a);
					} else {
						a = a + 1;
					}
				}
			}
		}

		sc.close();
	}
}