[백준] 11653 소인수분해 자바

📎 문제 출처

---

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

📌 문제 설명

---

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

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

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

❓ 풀이 방법

---

소인수분해는 소수로 이루어지기 때문에 에라토스테네스의 체 알고리즘을 이용해 isPrime 배열에 소수인 수들을 표시해 두고 나서 주어진 N이 1보다 작아질 때까지 계속 소수로 나누었다.

📌 Code

---

package com.ll;

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

public class Main {
    static boolean[] isPrime = new boolean[10000001];

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       int N = Integer.parseInt(br.readLine());

       prime();

       while(N > 1) {
           for(int i = 2; i <= N; i++) {
               if(isPrime[i] && N % i == 0) {
                   N = N / i;
                   System.out.println(i);
                   break;
               }
           }
       }
    }

    public static void prime() {
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for(int i = 2; i <= Math.sqrt(10000000); i++) {
            if(isPrime[i]) {
                for(int j = i * i; j <= 10000000; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}