[BOJ] 11653: 소인수분해(JAVA)

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

11653번: 소인수분해

문제

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

 

[문제 풀이]

소인수분해 문제의 기본 토대는 2부터 N까지 모든 수를 나눠보면서 나머지가 0일 경우 그 값을 출력하는 것인데, 수행시간을 조금 줄여보고자 다음 특성을 이용하기로 했다.

 

N을 두 개이상의 인수로 나타낼 수 있을 때 항상 인수 중 한 개 이상은 반드시 √N보다 작거나 같다는 특성을 이용해, 반복문의 범위를 2부터(1은 인수로 안치므로 2부터 시작) √N까지 진행시키며 해당 수로 N을 나누어 본다.

 

반복문 범위를 나타낼 변수를 i라 하면, N이 i로 나누어 떨어지면 해당 수를 print한다. 그리고 N 값을 N을 i로 나눈 몫, 즉 N = N/i 로 변경한다. 이 과정을 N이 더이상 i로 나누어 떨어지지 않을 때 까지 진행하며, N이 i로 나누어떨어지지 않으면 i를 1 증가시켜 위 과정을 반복한다. i값의 범위는 2~√N이다.

 

i가 √N일때까지 위 과정을 반복 후 종료된 후에도 N이 1이 아니라면 N을 print하고 종료한다. 1인 경우는 인수로 치지 않으니 출력하지 않는다.

 

 

 

[코드]

import java.util.*;

public class Main {
    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
    
      int N = sc.nextInt();
      for(int i = 2; i <= Math.sqrt(N); i++) {
          while(N % i == 0) {
             System.out.println(i);
             N /= i;
          }
      }
      
     if(N != 1) {
         System.out.println(N);
     }
   }
}