Goldbach Split

Difficulty: 1400 3000 ms 128 MB

math number-theory

Every even N ≥ 4 (in this range) can be written as a sum of two primes. Print the split with the smallest first prime.

Input: one even integer N.

Output: two primes p q with p + q = N and p minimal.

Constraints:

• 4 ≤ N ≤ 10⁷
• N is even

Sample Tests

10

3 7

4

2 2

Read the Editorial