728x90
난이도 - 실버 3
문제
양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.
출력
각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.
728x90
100000까지의 소수판별 배열을 생성한다(primes)
입력값을 하나씩 받아 가장 작은 소수부터 그 소수로 나누어 떨어지지 않을 때까지 나누기를 실행한다.
import java.io.*;
public class Main2312 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
boolean[] primes = sieveOfEratosthenes(100000);
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
int N = Integer.parseInt(br.readLine());
for (int i = 2; i <= N; i++)
if (!primes[i]) {
int count = 0;
while (N % i == 0) {
count++;
N /= i;
}
if (count != 0)
sb.append(i + " " + count + '\n');
}
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
static boolean[] sieveOfEratosthenes(int max) {
boolean[] isPrime = new boolean[max + 1];
for (int i = 2; i * i <= max; i++)
if (!isPrime[i]) {
for (int j = i * i; j <= max; j += i)
isPrime[j] = true;
}
return isPrime;
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 15814번(야바위 대장) - StringBuilder.setCharAt() (0) | 2024.06.25 |
---|---|
[백준 자바] 1124번(언더프라임) - 소인수 개수가 소수인 수 (0) | 2024.06.25 |
[백준 풀이] 1747번(소수&팰린드롬) (0) | 2024.06.25 |
[백준 자바] 21919번(소수 최소 공배수) (0) | 2024.06.24 |
[백준 자바] 7789번(텔레프라임) - 소수 판정 (0) | 2024.06.24 |