알고리즘
[백준 알고리즘] 11653 - 소인수분해
DevBee
2021. 6. 21. 06:12
https://www.acmicpc.net/problem/11653
11653번: 소인수분해
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
www.acmicpc.net
문제는 위와 같으며 주어진 숫자를 2부터 주어진 수의 제곱근까지 순서대로 반복하며 나눌 때 나머지가 0인 수를 찾아 출력하는 방식으로 문제를 해결할 수 있습니다.
자바 코드는 다음과 같습니다.
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));
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= Math.sqrt(n); i++) {
// 해당 숫자로 나누어지는 경우
while (n % i == 0) {
sb.append(i).append("\n"); // 출력 문자 저장
n /= i; // 나눈 몫으로 n 변경
}
}
// 나눌 때 사용된 소수 출력
System.out.print(sb);
// 제곱근까지만 나누는 수로 사용했기 때문에 남은 수 출력
if (n != 1) {
System.out.println(n);
}
}
}