Check If a Number Is Sum of Two Primes (C, C++, Java, Python)

Given a number N, the task is to check whether N can be expressed as the sum of two prime numbers and, if so, print all valid prime pairs.

What the Problem Is Asking

A prime number is any integer greater than 1 with no divisors other than 1 and itself. The set {2, 3, 5, 7, 11, 13, ...} is infinite. The question is: for a given N, does there exist a pair (p, q) where both are prime and p + q = N?

This connects to Goldbach’s conjecture, which states that every even integer greater than 2 can be written as the sum of two primes. Proposed in 1742, it has been verified computationally up to very large numbers but remains unproven in full generality. For placement and interview settings, treat it as a pattern you apply, not a theorem you prove.

Two observations reduce the search space before writing any code:

• Pairs are symmetric: (3, 31) and (31, 3) describe the same decomposition. Iterating i from 2 to N/2 covers each pair exactly once.
• For odd N, one prime in the pair must be 2. All other primes are odd, and odd + odd is always even. So for odd N, the only candidate is the pair (2, N-2).

Algorithm 1: Trial Division

The direct approach iterates i from 2 to N/2. For each i, it checks whether both i and N - i are prime using trial division.

How trial division works

To test if num is prime, divide it by every integer d from 2 up to sqrt(num). If any d divides num evenly, num is composite. The loop stops at sqrt(num) because if num = a * b and both factors exceed sqrt(num), their product would be greater than num.

• Time per primality check: O(sqrt(num))
• Outer loop iterations: N/2
• Overall per query: O(N * sqrt(N))

For N up to a few thousand, this is fast enough for a single online-assessment test case. For N in the millions, or for many queries, the sieve is worth setting up.

Algorithm 2: Sieve of Eratosthenes

The Sieve of Eratosthenes precomputes all primes up to N in a single preprocessing pass.

How the sieve works

• Step 1: Create a boolean array sieve[0..N], initially all true.
• Step 2: Set sieve[0] and sieve[1] to false.
• Step 3: For each i from 2 to sqrt(N): if sieve[i] is still true, mark all multiples of i from i*i onward as false.
• Step 4: After the pass, sieve[k] is true if and only if k is prime.

Once built, a primality check is a single array lookup: O(1). The outer loop to find all prime pairs runs in O(N), for a total of O(N log log N) including sieve construction. For multiple queries over the same range, build the sieve once and reuse it.

Code Implementations

C

#include <stdio.h>
#include <math.h>

int isPrime(int num) {
    if (num < 2) return 0;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

void checkSumOfPrimes(int n) {
    int found = 0;
    for (int i = 2; i <= n / 2; i++) {
        if (isPrime(i) && isPrime(n - i)) {
            printf("%d + %d\n", i, n - i);
            found = 1;
        }
    }
    if (!found)
        printf("%d cannot be expressed as a sum of two primes.\n", n);
}

int main() {
    int n;
    scanf("%d", &n);
    checkSumOfPrimes(n);
    return 0;
}

C++ (trial division)

#include <iostream>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

void checkSumOfPrimes(int n) {
    bool found = false;
    for (int i = 2; i <= n / 2; i++) {
        if (isPrime(i) && isPrime(n - i)) {
            cout << i << " + " << (n - i) << "\n";
            found = true;
        }
    }
    if (!found)
        cout << n << " cannot be expressed as a sum of two primes.\n";
}

int main() {
    int n;
    cin >> n;
    checkSumOfPrimes(n);
    return 0;
}

C++ (Sieve of Eratosthenes)

#include <iostream>
#include <vector>
using namespace std;

vector<bool> buildSieve(int n) {
    vector<bool> sieve(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i)
                sieve[j] = false;
        }
    }
    return sieve;
}

void checkSumOfPrimesSieve(int n) {
    vector<bool> sieve = buildSieve(n);
    bool found = false;
    for (int i = 2; i <= n / 2; i++) {
        if (sieve[i] && sieve[n - i]) {
            cout << i << " + " << (n - i) << "\n";
            found = true;
        }
    }
    if (!found)
        cout << n << " cannot be expressed as a sum of two primes.\n";
}

int main() {
    int n;
    cin >> n;
    checkSumOfPrimesSieve(n);
    return 0;
}

Java

import java.util.Scanner;

public class PrimeSum {
    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; (long) i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    static void checkSumOfPrimes(int n) {
        boolean found = false;
        for (int i = 2; i <= n / 2; i++) {
            if (isPrime(i) && isPrime(n - i)) {
                System.out.println(i + " + " + (n - i));
                found = true;
            }
        }
        if (!found)
            System.out.println(n + " cannot be expressed as a sum of two primes.");
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        checkSumOfPrimes(n);
        sc.close();
    }
}

Python

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def check_sum_of_primes(n):
    found = False
    for i in range(2, n // 2 + 1):
        if is_prime(i) and is_prime(n - i):
            print(f"{i} + {n - i}")
            found = True
    if not found:
        print(f"{n} cannot be expressed as a sum of two primes.")

n = int(input())
check_sum_of_primes(n)

Worked Examples

Two inputs traced step by step.

N = 34 (four valid pairs)

The outer loop runs from i = 2 to i = 17 (since 34 / 2 = 17).

• i = 2: isPrime(2) = true. isPrime(32): 32 = 2 x 16, composite. Skip.
• i = 3: isPrime(3) = true. isPrime(31): 31 is not divisible by 2, 3, or 5; sqrt(31) is approximately 5.57. Prime. Print (3, 31).
• i = 5: isPrime(5) = true. isPrime(29): 29 is not divisible by 2, 3, or 5; sqrt(29) is approximately 5.38. Prime. Print (5, 29).
• i = 7: isPrime(7) = true. isPrime(27): 27 = 3 x 9, composite. Skip.
• i = 11: isPrime(11) = true. isPrime(23): 23 is not divisible by 2 or 3; sqrt(23) is approximately 4.79. Prime. Print (11, 23).
• i = 13: isPrime(13) = true. isPrime(21): 21 = 3 x 7, composite. Skip.
• i = 17: isPrime(17) = true. isPrime(17) = true. Print (17, 17).

Output: four pairs: (3, 31), (5, 29), (11, 23), and (17, 17).

N = 11 (no valid pair)

The outer loop runs from i = 2 to i = 5 (since 11 / 2 = 5 in integer division).

• i = 2: isPrime(2) = true. isPrime(9): 9 = 3 x 3, composite. Skip.
• i = 3: isPrime(3) = true. isPrime(8): 8 = 2 x 4, composite. Skip.
• i = 4: isPrime(4): 4 = 2 x 2, composite. Skip.
• i = 5: isPrime(5) = true. isPrime(6): 6 = 2 x 3, composite. Skip.

Output: “11 cannot be expressed as a sum of two primes.” This confirms the odd-N rule: the only candidate is (2, 9), but 9 is not prime.

Edge Cases Worth Knowing

Input	What happens
N = 2	Loop runs from i = 2 to i = 1 — zero iterations. No pair.
N = 3	Loop runs from i = 2 to i = 1 — zero iterations. No pair.
N = 4	i = 2: isPrime(2) = true, isPrime(2) = true. One pair: (2, 2).
N = 5	i = 2: isPrime(2) = true, isPrime(3) = true. One pair: (2, 3).
N odd, prime	Only check i = 2; if N - 2 is prime, that is the sole pair.

Three takeaways from the table:

• N = 2 and N = 3 produce no pairs. The algorithm handles them correctly without special cases.
• The smallest N with a valid pair is N = 4, giving the pair (2, 2).
• For any odd N, the algorithm never needs more than one useful candidate — the pair starting with 2.

Mastering iteration bounds and primality logic is part of the data structures interview repertoire that companies test at the online assessment stage. A similar boundary-check pattern applies when scanning arrays for minimum and maximum values.

Why the Precompute Trade-off Matters Beyond This Problem

The choice between trial division and the sieve here captures a universal design decision: compute once and look up fast versus compute on demand and skip the setup cost. Trial division wins for a single query on a small input. The sieve wins when the same range is queried many times, because the O(N log log N) setup cost is paid once.

That same reasoning shows up in AI application engineering. LLM inference pipelines face the identical split: precompute and cache document embeddings (sieve logic, pay once) versus embed each document at query time (trial division logic, pay every time). Query volume is the deciding factor. Knowing which regime you are in, and whether the setup cost is justified, is the trade-off analysis that separates a junior from a senior in those roles.

If the primality algorithm above is the preparation layer, TinkerLLM at ₹299 is the application layer: a sandbox where you can take the same precompute-versus-compute decision and apply it to real LLM API calls, not just textbook examples.