(JAVA) 백준 6588번 : 골드바흐의 추측

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

 

 

대표적인 에라토스체네스의 체 를 활용한 문제이다.

 

난이도는 크게 어렵지 않은데

 

생각보다 실수로 인해 틀릴 수 있는 문제

 

 

헷갈린 것 중

 

 

Q. n = a + b 일 때, a 와 b는 같은 숫자여도 되는가?

A. 된다. 6 = 3 + 3 일 때도 성립한다.

 

 

Q. 홀수 중에 1은 안되고 3부터 인가?

A. "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 즉, 3부터 가능.

 

 

끝이다.

 

매커니즘

---

  1)  에라토스체네스의 체를 이용하여 boolean[1000001] 배열(1 ~ 1,000,000) 로 소수 구분하기.

  *** 2 이상 1000 이하의 수만 가지고 구할 수 있음. n = 1000000 일 때, n의 제곱근은 1000이므로

 

 

  2)  입력 값 - 3 부터 3까지 for문을 사용하여 높은 값 부터 시작.

    그래서 (i) 와 (입력값 - i) 둘 다 소수인지 찾는다.

 

 

ex) n = 8인 경우,

i = 5, 4, 3

입력값 - i  = 3, 4, 5

 

 

i 와 입력값 - i 가 소수인지 체크해서 둘 다 소수이면 그것이 정답.

*** 높은 값부터 내려오기 때문에 처음으로 발견한 값이 두 값의 차 가 가장 클 것이다.

 

 

  3)  찾으면 그대로 출력. 못찾으면 못찾는 경우에 대한 출력 처리

 

 

 

 

 

이상입니다.

 

감사합니다.

 

 

소스코드

---