[BOJ6588] 골드바흐의 추측
문제 설명
코드 리뷰
에라토스테네스의 체를 할 줄 아느냐 모르냐보다 테스트케이스를 입력받기전에 딱 한번 에라토스테네스의 체로 모든 소수를 뽑아놓고 시작하느냐 안하느냐가 중요한 문제인듯.
근데 에라토스테네스의 체를 배우면, 사전에 전처리를 하는 부분도 많이들 연습 하시니깐 어려운 문제는 아니었을 것 같다.
또한 전처리와 에라토스테네스의 체를 할 줄 알면, 그 이후는 답을 구했는데도 계속 보는 경우만 아니면 어떻게 풀어도 대부분 시간초과 걱정은 없을 것 같다.
문제가 답이 여러개일 경우에는 두 항의 차가 제일 작은게 아니라 큰 것을 구하라 했으니깐 앞에서부터 탐색하다가 답이 구해지면 더 이상 볼 필요 없이 바로 탈출하면 된다.
import java.io.*;
import java.util.*;
public class BOJ6588_골드바흐의추측 {
static boolean[] bd = new boolean[1000001];
static int N;
public static void main(String[] args) throws Exception {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
pp();
while(true) {
N = Integer.parseInt(br.readLine());
boolean flg = false;
if(N==0) break;
for(int i=3; i<N; i++) {
if(bd[i]) continue;
if(!bd[N-i]) {
flg = true;
sb.append(N+" = ").append(i).append(" + ").append(N-i).append("\n");
break;
}
}
if(flg == false) sb.append("Goldbach's conjecture is wrong\n");
}
System.out.println(sb);
}
static void pp() {
for(int i=2; i<=1000000; i++) {
if(bd[i]==true) continue;
for(int j=2; j*i<=1000000; j++) {
bd[i*j]=true;
}
}
}
}
댓글남기기