[백준11653] 소인수분해 / Java

문제주소 :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

 

<풀이법>

▒ 한줄 개념: 에라토스테네스의 체 ▒ 

주어진 수에 대해서 소인수분해를 하면 되는 문제로, 어려운 문제는 아닙니다.

하지만 이 문제에서 좀 더 중요한 것은, '소수들을 어떻게 결정하는가' 일 것입니다.

기본적으로 소수를 찾아내는 방식을 사용하며 시간초과가 발생할 수 있으니, '에라토스테네스의 체' 알고리즘을 사용하면 소수를 쉽게 결정해낼 수 있습니다. 

 

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class _11653_Factorization {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int target = sc.nextInt();
        boolean check[] = new boolean[target+1];
        for(int i = 2; i < check.length; i++){
            if(!check[i]){
                for(int j = i*2; j< check.length; j+=j){
                    check[j] = true;
                }
                while(target % i == 0){
                    System.out.println(i);
                    target = target / i;
                }
            }
        }
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest