반응형
이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.
문제 핵심
- N : 짝수
- 2 < N <= 1,000,000
- 두 개의 소수의 합이다.
- 순서만 다른 것은 같은 파티션이다.
풀이 과정
다음 문제는 소수를 먼저 찾아서 합을 구하면된다.
즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.
소수 찾기 ( 에라토스테네스의 체 ) - JAVA
에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.( 고대 그리수 수학자 에라토스테네스가 발견 ) 알고리즘다음과 같은 알고리즘을 따른다.0 ~ 50 까지의 수를 찾고자 할
p-coding.tistory.com
1. 소수 찾기
먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )
private static void sieveOfEratosthenes(int num) {
isPrime = new boolean[num + 1];
for (int i = 2; i <= num; i++) {
isPrime[i] = true;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (!isPrime[i]) continue;
for (int j = i + i; j <= num; j += i) {
isPrime[j] = false;
}
}
}
2. 골드 바흐 파티션 구성
1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )
2. 둘 다 소수일 때 count를 증가시킨다.
3. count를 반환한다.
private static int findGBPartitions(int evenNum) {
if(evenNum < 4 || evenNum % 2 != 0) {
throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
}
int count = 0;
for (int i = 2; i <= evenNum / 2; i++) {
if(isPrime[i] && isPrime[evenNum - i]) {
count++;
}
}
return count;
}
미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.
이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static boolean[] isPrime;
public static void main(String[] args) throws IOException {
solve();
}
private static void solve() throws IOException {
sieveOfEratosthenes(1000000);
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
for(int i = 0;i<N;i++){
int num = Integer.parseInt(bufferedReader.readLine());
String result = String.valueOf(findGBPartitions(num));
stringBuilder.append(result)
.append("\n");
}
System.out.println(stringBuilder);
}
private static void sieveOfEratosthenes(int num) {
isPrime = new boolean[num + 1];
for (int i = 2; i <= num; i++) {
isPrime[i] = true;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (!isPrime[i]) continue;
for (int j = i + i; j <= num; j += i) {
isPrime[j] = false;
}
}
}
private static int findGBPartitions(int evenNum) {
if(evenNum < 4 || evenNum % 2 != 0) {
throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
}
int count = 0;
for (int i = 2; i <= evenNum / 2; i++) {
if(isPrime[i] && isPrime[evenNum - i]) {
count++;
}
}
return count;
}
}
반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 11866번 문제 ] 요세푸스 문제 0 (2) | 2025.03.01 |
|---|---|
| [ 백준 2164번 문제 ] 카드2 (0) | 2025.02.27 |
| [ 백준 28278번 문제 ] 스택 2 - JAVA (1) | 2025.02.04 |
| [ 백준 28116번 문제 ] 선택 정렬의 이동 거리 (2) | 2024.12.27 |
| [ 백준 23881번 문제 ] 알고리즘 수업 - 선택 정렬 1 (0) | 2024.12.17 |
