← TCS questions
CodingReported in a candidate post, Aug 2019

Sum of two primes

Filed under TCS · Also reported at Ongrid

Free read 2 of 3

Confirm if inputs are always even numbers greater than 2, and what format the output should take (boolean or the prime pair).

The question

Write a function to check if a given integer greater than 2 can be expressed as the sum of two prime numbers according to Goldbach's conjecture.

Constraints

  • 4 <= n <= 10^5
  • n is even
  • Time limit: 1.0s

Examples

Input
n = 34
Output
True
Why
34 can be expressed as the sum of 3 and 31 (both prime numbers).

Approach

  1. Confirm if inputs are always even numbers greater than 2, and what format the output should take (boolean or the prime pair).

Solution

O(n log log n) time, O(n) space

Python
def is_sum_of_two_primes(n: int) -> bool:
    if n <= 3:
        return False
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for p in range(2, int(n**0.5) + 1):
        if sieve[p]:
            for i in range(p * p, n + 1, p):
                sieve[i] = False
    for i in range(2, n // 2 + 1):
        if sieve[i] and sieve[n - i]:
            return True
    return False

Tips

  • What they are testing: Tests primary prime-checking logic, boundary conditions around small even numbers, and efficient lookup.
  • Common mistake: Failing to precompute primes using a Sieve, leading to Time Limit Exceeded for larger inputs.

Related TCS questions

Collected from public candidate posts and coding forums. Updated Nov 2026.