[BOJ/백준 - 6588] 골드바흐의 추측

문제 출처: https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

---

	public class BOJ_6588 {
	static int[] arr = new int[1000001]; // 0 소수, 1: 소수아님
	public static void main(String[] args) throws IOException {
	// INPUT & INIT
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	// SET PRIME NUMBERS
	for(int i=2; i<=500000; i++){
	if(arr[i] == 1){continue;}
	for(int j=2; j*i<=1000000; j++){
	arr[i*j]++;
	}
	}
	// CALCULATE
	int target = 0;
	while((target = Integer.parseInt(br.readLine())) != 0){
	boolean checker = false;
	for(int i=3; i<1000001; i+=2){
	if(arr[i]==0 && arr[target-i]==0){
	checker = true;
	sb.append(target)
	.append(" = ")
	.append(i)
	.append(" + ")
	.append(target-i)
	.append("\n");
	break;
	}
	}
	if(checker == false){
	sb.append("Goldbach's conjecture is wrong.").append("\n");
	}
	}
	System.out.println(sb);
	}
	}

view raw BOJ_6588.java hosted with ❤ by GitHub

---

일단 먼저 소수 세팅을 하고 (에라토스테네스의 체)

3부터 홀수를 체크해가면서 

반복문 i ,  입력받은 수 - 반복문 i  가 소수인지 체크한다

 

원래는 먼저 떠오른 투포인터로 풀었는데 속도가 많이 느리게 나온거같아 다시 풀었다 (통과는 했음)

밑에는 투포인터로 처음에 제출한 코드이다 

	public class Temp {
	static int[] primes = new int[1000001];
	public static void main(String[] args) throws Exception{
	// INPUT & INIT
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// set Prime Numbers
	for(int i=2; i<Math.sqrt(1000001); i++) {
	if(primes[i] == 0) {
	for(int j=2; j*i<1000001; j++) {
	primes[i*j] = 1;
	}
	}
	}
	int target = 0;
	while((target = Integer.parseInt(br.readLine())) != 0) {
	// SETTING
	int left = 3;
	int right = 0;
	for(int i=target; i>=3; i--) {
	if(i%2==1 && primes[i] == 0) {
	right = i;
	break;
	}
	}
	while(true) {
	// 종료조건 1. 값을 찾았을때
	if(left+right == target) {
	System.out.println(target+" = "+left+" + "+right);
	break;
	}
	// 종료조건 2. 답이 없을 경우
	if(left > right) {
	System.out.println("Goldbach's conjecture is wrong.");
	break;
	}
	if(left+right < target) {
	while(true) {
	left++;
	if(left%2==1 && primes[left] == 0) {
	break;
	}
	}
	}else if(left+right>target) {
	left = 2;
	while(true) {
	right--;
	if(right%2==1 && primes[right] == 0) {
	break;
	}
	}
	}
	}
	}
	}
	}

view raw Temp.java hosted with ❤ by GitHub