백준 11653번 소인수분해 자바 Java (☆공부 258일차)

백준 8단계 3번 문제 - 11653 소인수분해

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

11653번: 소인수분해

 

 

 

---

백준 11653번 문제 소인수분해

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	86629	46707	36219	52.479%

문제

정수 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

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/51

백준 11653번 소인수분해 / 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2

6달 전에 푼 문제

 

https://gimbalja.tistory.com/412

에라토스테네스의 체

어디까지 반복문을 돌릴지 생각할 때, 소수의 대칭성을 고려해서 돌린다

소수의 대칭성을 위의 링크에 설명해두었다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
 
        for(int i = 2; i*i <= N; i++) {
            while(N % i == 0) {
                sb.append(i).append("\n");
                N /= i;
            }
        }
        if(N > 1) {    // 2 이상으로 남았을 때
            sb.append(N);
        }
        
        System.out.println(sb);
        br.close();
    }
 
}
 

 

 

 

---