C++ Program To Check Whether A Number Can Be Express As Sum Of Two Prime Numbers Or Not

This article explores how to determine if a given integer can be expressed as the sum of two prime numbers using C++. In this article, you will learn the logic, implementation, and common pitfalls associated with solving this problem.

Problem Statement

The challenge is to write a C++ program that takes an integer as input and verifies if it can be represented as the sum of two prime numbers. This is a classic problem in number theory, relevant for understanding primality tests and number decomposition. For example, the number 10 can be expressed as 3 + 7 or 5 + 5, where 3, 5, and 7 are all prime numbers.

Example

Consider the input number 10.

The program should output:

10 can be expressed as sum of two prime numbers: 3 + 7

Or if no such pair exists for another number, it might output:

11 cannot be expressed as sum of two prime numbers.

Background & Knowledge Prerequisites

To understand this article, readers should be familiar with:

• C++ Basics: Variables, loops (for, while), conditional statements (if-else).
• Functions: Defining and calling user-defined functions.
• Prime Numbers: The definition of a prime number (a natural number greater than 1 that has no positive divisors other than 1 and itself).

Use Cases or Case Studies

Understanding how to decompose numbers into primes has several applications:

• Cryptography: Prime numbers are fundamental to many encryption algorithms like RSA.
• Number Theory Research: It's a stepping stone for exploring conjectures like Goldbach's Conjecture, which states that every even integer greater than 2 is the sum of two primes.
• Algorithmic Challenges: This problem is a common interview question or competitive programming task, testing logical thinking and basic algorithm design.
• Educational Tool: It serves as an excellent exercise for learning about function decomposition and optimizing loops.
• Resource Allocation: In some theoretical scheduling problems, breaking down a task (number) into two prime-sized sub-tasks might represent an optimal distribution.

Solution Approaches

We will focus on a straightforward approach involving a helper function to check for primality.

Approach 1: Helper Function for Primality Test

This approach involves creating a separate function isPrime() to check if a given number is prime. The main function then iterates through numbers from 2 up to half of the input number, checking if both the current number and its complement (input - current) are prime.

One-line summary: Iterate through possible first primes up to half the target number, and for each, check if both the current number and the remaining part are prime using a helper function.

// Check if a Number is Sum of Two Primes
#include <iostream> // For input/output operations
#include <cmath>    // For sqrt function

// Function to check if a number is prime
bool isPrime(int num) {
    // Step 1: Handle edge cases for primality
    if (num <= 1) {
        return false; // Numbers less than or equal to 1 are not prime
    }
    // Step 2: Check divisibility from 2 up to the square root of num
    // We only need to check up to sqrt(num) because if num has a divisor
    // greater than sqrt(num), it must also have one smaller than sqrt(num).
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) {
            return false; // If divisible, it's not prime
        }
    }
    // Step 3: If no divisors found, it's prime
    return true;
}

int main() {
    int n;
    // Step 1: Prompt user for input
    std::cout << "Enter a positive integer: ";
    std::cin >> n;

    // Step 2: Check if the number can be expressed as sum of two primes
    bool found = false; // Flag to track if a pair is found
    for (int i = 2; i <= n / 2; ++i) {
        // Step 3: Check if 'i' is prime
        if (isPrime(i)) {
            // Step 4: Check if 'n - i' is prime
            if (isPrime(n - i)) {
                // Step 5: If both are prime, print the result and set flag
                std::cout << n << " can be expressed as sum of two prime numbers: " << i << " + " << (n - i) << std::endl;
                found = true;
                break; // Found a pair, no need to check further
            }
        }
    }

    // Step 6: If no pair was found after checking all possibilities
    if (!found) {
        std::cout << n << " cannot be expressed as sum of two prime numbers." << std::endl;
    }

    return 0; // Indicate successful execution
}

Run

Sample Output:

Enter a positive integer: 10
10 can be expressed as sum of two prime numbers: 3 + 7

Enter a positive integer: 11
11 cannot be expressed as sum of two prime numbers.

Enter a positive integer: 34
34 can be expressed as sum of two prime numbers: 3 + 31

Stepwise Explanation:

1. isPrime(int num) Function:
   • It takes an integer num and returns true if num is prime, false otherwise.

It first handles base cases: numbers 1 or less are not prime.

It then iterates from 2 up to the square root of num. If num is divisible by any number in this range, it's not prime.

If the loop completes without finding any divisors, num is prime.

1. main() Function:
   • It prompts the user to enter a positive integer n.

A boolean flag found is initialized to false.

It then enters a for loop that iterates from i = 2 up to n / 2. The loop goes up to n/2 because if one prime p1 is greater than n/2, then the other prime p2 (n - p1) must be less than n/2. To avoid redundant checks (e.g., checking 3+7 and then 7+3), we only need to check one side.

Inside the loop, it first calls isPrime(i) to check if the current number i is prime.

If i is prime, it then calculates the complement (n - i) and calls isPrime(n - i) to check if the complement is also prime.

If both i and n - i are prime, it means n can be expressed as the sum of two primes. The program prints the pair, sets found to true, and breaks out of the loop because we've found a valid pair.

After the loop, if found is still false, it means no such pair of prime numbers was found for n, and an appropriate message is printed.

Conclusion

Determining if a number can be expressed as the sum of two prime numbers involves a straightforward application of a primality test. By systematically checking pairs, we can efficiently find a solution or conclude that none exists. This problem highlights the importance of modular programming, using functions to encapsulate distinct logic like primality testing.

Summary

• The problem asks to check if a number N can be written as P1 + P2, where P1 and P2 are prime.
• A helper function isPrime() is crucial for efficiently checking if a number is prime.
• The isPrime() function checks for divisors up to the square root of the number for optimization.
• The main logic iterates from 2 up to N/2, checking if both i and N - i are prime.
• The first pair of prime numbers found that sum up to N is sufficient to confirm the condition.
• This problem is a good example of applying basic number theory concepts and function decomposition in C++.