https://www.acmicpc.net/problem/11653
문제
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
출력
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.
소인수분해는 소수로 이루어지기 때문에 에라토스테네스의 체 알고리즘을 이용해 isPrime 배열에 소수인 수들을 표시해 두고 나서 주어진 N이 1보다 작아질 때까지 계속 소수로 나누었다.
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;
}
}
}
}
}