문제
Goldbach's conjecture says that every even number greater than 2 is the sum of two primes. It has never been proven, but it has been checked far beyond the numbers here. Often there are several ways: 28 = 5 + 23 = 11 + 17. Find the one whose smaller prime is as small as possible.
Implement goldbach_partition(n).
Trying p = 2, 3, 5, ... and testing whether n − p is prime finds the answer quickly, because a small p almost always works. Testing a number up to 10^9 for primality by trial division only needs divisors up to about 31,623.
Input
n: An even number greater than 2.
Output
Return [p, q] where p and q are primes, p + q = n, p ≤ q, and p is the smallest prime for which this works.
제약 조건
4 ≤ n ≤ 10^9, n is even
예시
입력:
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 and 28 − 3 = 25 are not prime, but 28 − 5 = 23 is, so the answer is [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};
설명
The only option is 2 + 2, so the answer is [2, 2].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
Try p = 2, 3, 4, ... and stop at the first p where both p and n − p are prime.
힌트 2
A prime test only needs to try divisors up to the square root.
힌트 3
Since you stop at the smallest p, p ≤ n − p comes for free.
예상 복잡도
O(k √n) time where k is the number of candidates tried, O(1) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.