Ctrl K

A Number as Two Primes

Medium
You are given an integer total. Find every way to write it as a sum of two primes x + y with x ≤ y. Return the list of pairs [x, y] sorted by increasing x. If there is no way, return an empty list. Recall that a prime is greater than 1 and divisible only by 1 and itself.
Example 1
total=16 → [[3, 13], [5, 11]]

16 = 3 + 13 = 5 + 11. The pair 7 + 9 does not count because 9 is not prime.

Example 2
total=9 → [[2, 7]]

The sum is odd, so one summand must be 2 and the other is 7, which is prime.

Example 3
total=27 → []

The only candidate is 2 + 25, but 25 = 5 · 5 is not prime, so there are no pairs.

Constraints
  • 1 ≤ total ≤ 5 · 10⁶
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsPrimes Below a Bound MediumPrimes Along Grid Rays MediumWhere the Product Adds Up EasyPhoto Frames of the Same Shape MediumGrid Points Under Circles Medium
loading Python…
Input
total=16
Expected
[[3, 13], [5, 11]]

Run checks the first 3 tests in your browser. Submit checks all 55 tests on the server, hidden ones included.