Algorithm - 소인수분해 (Java - 쉬운 풀이)

🌴 문제

---

문제

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

입력

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

출력

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

예제 입력 1 복사

72

예제 출력 1 복사

2
2
2
3
3

예제 입력 2 복사

3

예제 출력 2 복사

3

예제 입력 3 복사

6

예제 출력 3 복사

2
3

예제 입력 4 복사

2

예제 출력 4 복사

2

예제 입력 5 복사

9991

예제 출력 5 복사

97
103

 

 

 

 

 

 

 

 

🌴 문제 분석

---

package Backjoon;

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

public class day25 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// 정수 N이 주어졌을 때, 소인수분해하는 프로그램

		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		
		
		// <1번 풀이>
//		//n이 1이 될 때까지 반복
//		int i =2;
//		while (n != 1) {
//			// i가 n의 약수이면 나누고 출력
//			if (n % i == 0) {
//				n /= i;
//				sb.append(i + "\n");
//			} else {
//				i++;
//			}
//		}
//		
//		System.out.print(sb);
		
		
		
		
		//<2번 풀이>
		for (int i = 2; i <= Math.sqrt(n); i++) { // 에라토스테네스의 체.
			while (n % i == 0) {
				sb.append(i).append('\n');
				n /= i;
			}
		}
		
		if ( n!= 1) {     // 인수를 갖고 있는데 출력을 못하는 것을 방지하기 위해 한번 더 출력 
			sb.append(n);
		}
		System.out.print(sb);
	}

}

----
72
2
2
2
3
3

 

 

 

 

 

 

# 참고

소인수분해 - https://mathbang.net/200#gsc.tab=0

https://st-lab.tistory.com/152

[백준] 11653번 : 소인수분해 - JAVA [자바]

소인수분해, 소인수분해 하는 법, 소인수 뜻