[백준] code.plus(수학,JAVA)6588번, 골드바흐의 추측

문제 링크

6588번: 골드바흐의 추측

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은 2가지입니다.

1. 소수를 구하는 방법

2. b-a가 최소의 연산으로 가장 큰 값을 알아내는 것

소수를 구하는 방법에서는 저는 에라토스테네스의 체를 이용하여 구하였습니다.

에라토스테네스의 체를 간단하게 설명하겠습니다.

최대값보다 작은 값(0과 1은 제외)들에서 자신을 빼고 배수의 숫자들은 소수인지 아닌지 판단하는 것입니다.

아래의 그림을 보면 이해가 편하실 겁니다.

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

더 자세한 내용은 제가 참고한 곳을 링크로 남기겠습니다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

b-a를 최소의 연산으로 얻어내려면 b는 무조건 소수 중 가장 큰 값이 되어야 하기 때문에 입력 값에 가까운 수부터 소수인지 확인하도록 하였습니다.

소수인 수를 확인할 때에도 입력값 =  a + b으로 0~n 범위가 아닌 n/2 ~ n범위에 소수를 찾도록 하는 것입니다.

 

문제에 해결알고리즘은

1. 소수를 확인하는 Boolean형 리스트를 만들었습니다.

2. 0과 1은 소수가 아니기 때문에 2번 false를 저장하였습니다.

3. 최대값이 1000000이므로 그 크기만큼 리스트에 true를 저장하였습니다.

4. 에라토스테네스의 체를 구현하여 리스트에 인덱스가 소수인지 아닌지를  저장하였습니다.

5. 입력값에 따라 b-a에서 b는 가장 큰 소수이므로 입력값/2 ~ 입력값 범위에서 가장 큰 소수를 찾고 그에 대응하는 a가 소수인지 확인하여 모두 소수이면 결과를 도출합니다.

6. 둘다 소수가 존재하지 않는다면 "Goldbach's conjecture is wrong." 출력되게 하였습니다.

 

• 소수를 확인하는 리스트를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 에라토스테네스의 체를 실행하는decimalCal함수를 만들었습니다.
• b-a가 가장 크고 a,b가 소수일 때 b를 구하는 goldbach 함수를 만들었습니다.
• BufferedWriter에 입력값에 따른 a,b의 소수값을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• decimalCal은 반복문을 통해 자신 제외한 배수들은 소수가 아니라는 것을 판단합니다.
• goldbach은 a,b가 소수이고 b-a가 가장 클 때 b를 반복문을 통해 구합니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static List<Boolean> list = new ArrayList<Boolean>();	//소수 확인 리스트
	static int maxValue = 1000000;	///최대값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        decimalCal();     	//함수 실행
        //---------입력값 저장 및 함수 실행-------------
        while(true) {
        	int num = Integer.parseInt(br.readLine());
        	if(num==0)
        		break;
        	int b = goldbach(num);		//함수 실행
        	int a = num - b;
        	if(b==-1) {	//두 소수로 만들수 없는 경우
        		bw.write("Goldbach's conjecture is wrong.\n");
        	}else {
            	//결과 BufferedWriter 저장
            	bw.write(num + " = " + a + " + " + b + "\n" );
        	}
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //-------b-a중 가장 컸을 때 b의 값을 구하는 함수--------
    public static int goldbach(int num) {
    	for(int i=num;i>=num/2;i--) {
        //a,b가 소수이고 b가 가장 큰 소수일 때
    		if(list.get(i) && list.get(num-i))
    			return i;
    	}
    	return -1;
    }
    //----에라토스테네스의 체 함수--------
    public static void decimalCal() {
        list.add(false);	//0은 소수 X
        list.add(false);	//1은 소수 X
        for(int i=2;i<=maxValue;i++) 
        	list.add(true);		//리스트 최대값만큼 초기화
        //-----소수이면 false, 소수 아니면 true-------
        for(int i=2;i*i<=maxValue;i++) {
        	if(list.get(i)) {
        		for(int j=i*i;j<=maxValue;j+=i)
        			list.set(j, false);
        	}
        }
    }
}