Algorithm/수학
백준 알고리즘 [자바] 골드 바흐의 추측 9020
한둥둥
2022. 10. 7. 15:30
골드 바흐의 추측 9020
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class Baekjoon9020 {
static boolean checkArr[]= new boolean[10001];
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException{
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
soloCheck();
for(int i=0;i<n;i++){
int n1 = scan.nextInt();
sumSolo(n1);
}
bw.flush();
bw.close();
scan.close();
}
static void sumSolo(int num)throws IOException{
int rt = num/2;
int lt = num/2;
while(true){
if(!checkArr[rt]&&!checkArr[lt]){
bw.write(lt+" "+rt+"\n");
break;
}
rt++;
lt--;
}
}
static void soloCheck(){
for(int i=2;i<checkArr.length-1;i++){
if(checkArr[i]) continue;
for(int j=i*i;j<checkArr.length;j+=i){
checkArr[j]=true;
}
}
}
}
1.우선적으로 소수 구하기 문제처럼 soloCheck배열을 통해서 배열이 소수인지 아닌지 판별을 해주었다.
이미 true인 아이들은 찾아서 들어 갈 필요가 없기 때문에 즉, 한번 쭉 이전에 지난간거여서 복잡도를 단축시키기위해 continue로 위로 올려주었다.
2. 그 후에 sumSolo라는 함수에서 더해주는 값을 찾았고 절반을 기준으로 플러스 마이너스 해주면서 해당하는 값이 소수인 경우에 출력되도록 만들어주었다. 절반값이 둘다 소수라면 두 수를 더해주면 내가 원하는 숫자가 나올 것이다. 왜냐면 동시에 lt,rt변수를 통해서 증가, 감소 시켜주기 때문이다. 이때 가장 먼저 빨리 등장하여 더해주는 값이 두 값 사이의 최소 값이 될 것이다.
이렇게까지만 생각하면 골드바흐는 쉬울수도?