Sum of two primes
Filed under TCS · Also reported at Ongrid
Free read 2 of 3Confirm 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
Confirm if inputs are always even numbers greater than 2, and what format the output should take (boolean or the prime pair).
Iterate i from 2 to n/2, and check if both i and n-i are prime by iterating up to each number.
Precompute all prime numbers up to n using the Sieve of Eratosthenes. Then iterate i and check if both i and n-i are in the prime set.
Handle odd numbers or numbers less than 4 gracefully if the constraints permit them.
Solution
O(n log log n) time, O(n) space
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.