All challenges
Medium 0 solved 0% acceptance

Goldbach Partition

Write an even number as the sum of two primes, using the smallest possible first prime.

What you'll learn

  • Write a trial-division prime test that stops at √n
  • Search candidates in increasing order and stop at the first hit
  • Return a pair in the required order

Problem

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.

Constraints

4 ≤ n ≤ 10^9, n is even

Examples

Example 1
Input:
n = 28

Expected output:
expected = [5, 23]
Input:
long long n = 28;

Expected output:
std::vector<long long> expected = {5, 23};
Input:
long n = 28;

Expected output:
long[] expected = new long[] {5, 23};

Explanation

28 − 2 = 26 and 28 − 3 = 25 are not prime, but 28 − 5 = 23 is, so the answer is [5, 23].

Example 2
Input:
n = 4

Expected output:
expected = [2, 2]
Input:
long long n = 4;

Expected output:
std::vector<long long> expected = {2, 2};
Input:
long n = 4;

Expected output:
long[] expected = new long[] {2, 2};

Explanation

The only option is 2 + 2, so the answer is [2, 2].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Try p = 2, 3, 4, ... and stop at the first p where both p and n − p are prime.

Hint 2

A prime test only needs to try divisors up to the square root.

Hint 3

Since you stop at the smallest p, p ≤ n − p comes for free.

Expected complexity

O(k √n) time where k is the number of candidates tried, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.