Check whether a number can be expressed as a sum of two prime numbers

Have you ever wondered if a given number can be written as the sum of two prime numbers? This is a common problem in number theory, often tested in coding interviews and competitive programming.

In this guide, we’ll explore how to check if a number N can be represented as the sum of two prime numbers using an optimized approach. We’ll also provide code implementations in C, C++, Java, and Python to help you master this concept.

What You’ll Learn:
✅ The logic behind summing two prime numbers
✅ Efficient algorithm to solve the problem
✅ Code implementations in multiple languages
✅ Suggested visuals for better understanding

Understanding the Concept

A prime number is a number greater than 1 that has only two factors: 1 and itself.

Example: Prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, …

To check if a number N can be represented as the sum of two prime numbers, we need to:

1. Iterate through possible prime numbers i (from 2 to N/2).
2. Check if i and (N - i) are both prime.
3. If both numbers are prime, print the pair.

Example Walkthrough

Let’s take N = 34 as an example:

34 can be represented as:

• 3 + 31 (Both are prime)
• 5 + 29 (Both are prime)
• 11 + 23 (Both are prime)
• 17 + 17 (Both are prime)

Thus, 34 can be expressed as the sum of two prime numbers in multiple ways. ✅

Optimized Algorithm for Checking Sum of Two Prime Numbers

Steps to follow:
Input the number N to be checked.
Loop from i = 2 to N/2.
Check if i is prime.
If i is prime, check if N - i is also prime.
If both numbers are prime, print them.
If no such pair exists, print that the number cannot be expressed as a sum of two primes.

🔹 Time Complexity: O(N√N), as we check prime status multiple times.
🔹 Optimized Approach: Use the Sieve of Eratosthenes for precomputing primes to reduce time complexity.

Code Implementations

1 C Program to Check if a Number is the Sum of Two Prime Numbers

#include <stdio.h>

// Function to check if a number is prime
int isPrime(int num) {
    if (num < 2) return 0;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

// Function to find pairs of prime numbers
void checkSumOfPrimes(int n) {
    int flag = 0;
    printf("Prime pairs for %d: \n", n);
    for (int i = 2; i <= n / 2; i++) {
        if (isPrime(i) && isPrime(n - i)) {
            printf("%d + %d\n", i, n - i);
            flag = 1;
        }
    }
    if (!flag) {
        printf("%d cannot be expressed as a sum of two prime numbers.\n", n);
    }
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    checkSumOfPrimes(num);
    return 0;
}

2 C++ Program to Check if a Number is the Sum of Two Prime Numbers

#include <iostream>
using namespace std;

// Function to check if a number is prime
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

// Function to check sum of two primes
void checkSumOfPrimes(int n) {
    bool found = false;
    cout << "Prime pairs for " << n << ": " << endl;
    for (int i = 2; i <= n / 2; i++) {
        if (isPrime(i) && isPrime(n - i)) {
            cout << i << " + " << (n - i) << endl;
            found = true;
        }
    }
    if (!found) {
        cout << n << " cannot be expressed as a sum of two prime numbers." << endl;
    }
}

int main() {
    int num;
    cout << "Enter a number: ";
    cin >> num;
    checkSumOfPrimes(num);
    return 0;
}

3 Java Program to Check if a Number is the Sum of Two Prime Numbers

import java.util.Scanner;

public class PrimeSum {
    // Function to check if a number is prime
    static boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    // Function to check sum of two primes
    static void checkSumOfPrimes(int n) {
        boolean found = false;
        System.out.println("Prime pairs for " + n + ": ");
        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 prime numbers.");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();
        checkSumOfPrimes(num);
        sc.close();
    }
}

4 Python Program to Check if a Number is the Sum of Two Prime Numbers

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def check_sum_of_primes(n):
    print(f"Prime pairs for {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 prime numbers.")

num = int(input("Enter a number: "))
check_sum_of_primes(num)

Conclusion

This article provided a comprehensive guide on checking if a number can be expressed as a sum of two prime numbers. The optimized approach ensures efficiency, making it ideal for large numbers.