[백준 Java]15711_환상의 짝궁_수학, 소수

🔗 문제링크 🔗

15711번: 환상의 짝꿍

---

🌟 생각 흐름 🌟

처음 문제를 보고 짝수와 홀수를 나눠서 생각했다.

1. 홀수의 경우 소수이기 위해서는 한 수가 무조건 2이고 다른 수고 sum-2 이어야 한다.

홀수가 되기 위해서는 짝수 + 홀수 이기 때문에 유일한 짝수이자 소수인 2를 무조건 포함해야 한다고 생각했고 나머지만 소수 판별하면 되겠네라고 생가하고 넘어갔다.

2. 짝수인 경우에는? 여기서 한번 고민을 했다 이걸 다 확인할 수는 없을 거 같은데.. 그래서 구글에 "소수의 합"을 검색하니 골드 바흐의 추측에 의해 2 이상의 모든 짝수는 모두 소수로 표기가 가능하다고 했다

 

그러면 이제 구현만 하면 된다. 보통 소수는 자신의 제곱근 범위까지 에라토스테네스의 체로 확인하고 해당 범위까지 소수로 체크되지 않으면 소수가 아니라고 생각한다. 따라서 2 × 10^12 *2 (두 수의 합)= 4 × 10^12 이고 제곱근을 구하면 2 × 10^6까지만 소수를 체크해 둔다. 그리고 소수라고 판단된 것은 모두 prime이라는 리스트에 넣는다.

 

이후에 실제 소수를 확인하기 위한 함수에서는 확인하려는 수가 이미 체크된 경우라면 빠르게 빠져나가게 하고 2 × 10^6 이상인 경우에는 prime이 가지고 있는 소수를 이용하여 체크하면서 소수인지 판별한다.

 

문제를 처음에 잘 접근했는데 왜 나는 A+B를 A*B를 했을까.. 배열 범위가 초과될 거 같아 소수인지 하나씩 다 판별하면 42%에서 에러가 난다. 92% 에서 에러가 난다면 1,1과 같은 엣지 케이스를 놓치고 있는 것이다. 뭔가 이상할 땐 천천히 다시 한번 문제를 읽는 연습을 해야겠다..

---

🍳 코드 🍳