문제
골드바흐의 추측은 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있다는 내용입니다. 아직 증명되지는 않았지만, 이 문제에 나오는 수보다 훨씬 큰 범위까지 성립함이 확인되었습니다. 나타내는 방법이 여러 가지인 경우도 많습니다. 예를 들어 28 = 5 + 23 = 11 + 17입니다. 그중 작은 쪽 소수가 가장 작은 것을 찾으세요.
goldbach_partition(n) 함수를 구현하세요.
p = 2, 3, 5, ... 순서로 시도하면서 n − p가 소수인지 확인하면 답을 금방 찾을 수 있습니다. 작은 p에서 거의 항상 성공하기 때문입니다. 10^9 이하의 수를 나눗셈으로 소수 판별할 때는 약 31,623까지만 나누어 보면 됩니다.
입력
n: 2보다 큰 짝수입니다.
출력
p와 q가 소수이고 p + q = n, p ≤ q이며, p가 이를 만족하는 가장 작은 소수가 되는 [p, q]를 반환합니다.
제약 조건
4 ≤ n ≤ 10^9, n은 짝수
예시
입력:
n = 28
예상 출력:
expected = [5, 23]
입력:
long long n = 28;
예상 출력:
std::vector<long long> expected = {5, 23};
입력:
long n = 28;
예상 출력:
long[] expected = new long[] {5, 23};
설명
28 − 2 = 26과 28 − 3 = 25는 소수가 아니지만 28 − 5 = 23은 소수이므로 답은 [5, 23]입니다.
입력:
n = 4
예상 출력:
expected = [2, 2]
입력:
long long n = 4;
예상 출력:
std::vector<long long> expected = {2, 2};
입력:
long n = 4;
예상 출력:
long[] expected = new long[] {2, 2};
설명
2 + 2밖에 방법이 없으므로 답은 [2, 2]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
p = 2, 3, 4, ... 순서로 시도해서 p와 n − p가 모두 소수인 첫 p에서 멈추세요.
힌트 2
소수 판별은 제곱근까지만 나누어 보면 됩니다.
힌트 3
가장 작은 p에서 멈추므로 p ≤ n − p는 저절로 만족됩니다.
예상 복잡도
시도한 후보 수가 k일 때 시간 O(k √n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.