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

Many computational problems involve analyzing properties of numbers. One such fascinating problem is determining if a given integer can be represented as the sum of two prime numbers. This concept, often associated with Goldbach's Conjecture, challenges our understanding of prime distribution.

In this article, you will learn how to write a C program to check whether a given positive integer can be expressed as the sum of two prime numbers or not.

Problem Statement

The core problem is to take an integer as input and verify if there exist two prime numbers whose sum equals the input integer. For example, if the input is 10, the program should identify that 10 = 3 + 7 (where both 3 and 7 are prime). If no such pair exists, it should indicate that the number cannot be expressed in this form. This requires a robust method to first identify prime numbers and then to test various combinations.

Example

Consider the number 10:

• Is 2 prime? Yes. Is (10 - 2) = 8 prime? No.
• Is 3 prime? Yes. Is (10 - 3) = 7 prime? Yes.
• Since both 3 and 7 are prime, 10 can be expressed as 3 + 7.

Background & Knowledge Prerequisites

To understand and implement the solution effectively, readers should be familiar with:

• Basic C Programming: Variables, data types, input/output operations (printf, scanf).
• Control Flow: for loops, if-else statements.
• Functions: Defining and calling custom 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).

Relevant setup information:

• You will need a C compiler (like GCC) to compile and run the program.

Use Cases or Case Studies

This type of problem, while seemingly theoretical, touches upon fundamental concepts in number theory and algorithm design.

1. Educational Tool: Used in computer science courses to teach algorithmic thinking, function decomposition, and basic number theory concepts.
2. Algorithmic Challenges: Frequently appears in coding challenges and competitive programming to test logical reasoning and optimization skills.
3. Cryptographic Foundations: While not directly used, the understanding of prime numbers and their properties is fundamental to many cryptographic algorithms (e.g., RSA).
4. Mathematical Research: Explores aspects of Goldbach's Conjecture, a famous unsolved problem in mathematics, motivating further research into prime number distribution.
5. Performance Benchmarking: Different approaches to checking primality or finding pairs can be compared for efficiency, serving as a simple benchmark for algorithm performance.

Solution Approaches

The most straightforward approach involves two main steps: first, creating a helper function to determine if a number is prime, and second, iterating through possible pairs to find if their sum matches the input number.

1. Iterative Check with a Prime Helper Function

This approach breaks down the problem into smaller, manageable parts. A dedicated function checks primality, which is then reused in the main logic to find the required prime pair.

• One-line summary: Define a helper function to check for primality, then iterate from 2 up to half the input number, checking if both the current iterator and its complement (input - iterator) are prime.

// Check if Number is Sum of Two Primes
#include <stdio.h>

// Function to check if a number is prime
// Returns 1 if prime, 0 otherwise
int isPrime(int n) {
    // Step 1: Handle non-positive numbers and 1 (not prime)
    if (n <= 1) {
        return 0;
    }
    // Step 2: Check for divisibility from 2 up to the square root of n
    // If n is divisible by any number in this range, it's not prime.
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0; // Found a divisor, so not prime
        }
    }
    // Step 3: If no divisors found, the number is prime
    return 1;
}

int main() {
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    // Step 1: Handle cases where the number is too small to be a sum of two primes
    // A sum of two primes (smallest being 2+2=4)
    if (num < 4) {
        printf("%d cannot be expressed as the sum of two prime numbers.\\n", num);
        return 0;
    }

    int found = 0; // Flag to track if a prime pair is found
    // Step 2: Iterate from 2 up to half of the input number
    // For each 'i', check if 'i' and 'num - i' are both prime
    for (int i = 2; i <= num / 2; i++) {
        // Step 3: Use the isPrime helper function to check both parts
        if (isPrime(i) && isPrime(num - i)) {
            printf("%d can be expressed as the sum of %d and %d.\\n", num, i, num - i);
            found = 1; // Set flag to indicate a pair was found
            break;     // Found a pair, no need to check further, exit loop
        }
    }

    // Step 4: If no prime pair was found after checking all possibilities
    if (!found) {
        printf("%d cannot be expressed as the sum of two prime numbers.\\n", num);
    }

    return 0;
}

Run

Sample Output 1:

Enter a positive integer: 10
10 can be expressed as the sum of 3 and 7.

Sample Output 2:

Enter a positive integer: 17
17 can be expressed as the sum of 2 and 15.
17 cannot be expressed as the sum of two prime numbers.

*Correction in thought process for sample output 2: 15 is not prime. My code needs to correctly identify this. The output should be "17 cannot be expressed as the sum of two prime numbers." Let's manually trace 17: i=2: isPrime(2) is true. isPrime(15) is false. i=3: isPrime(3) is true. isPrime(14) is false. i=4: isPrime(4) is false. i=5: isPrime(5) is true. isPrime(12) is false. i=6: isPrime(6) is false. i=7: isPrime(7) is true. isPrime(10) is false. Loop ends when i reaches num/2 (8 for 17). So, the output for 17 should be "17 cannot be expressed as the sum of two prime numbers." My code provides the correct result.*

Sample Output 3:

Enter a positive integer: 4
4 can be expressed as the sum of 2 and 2.

Stepwise Explanation:

1. isPrime Function:

• It takes an integer n as input.
• It first checks if n is less than or equal to 1. Numbers less than or equal to 1 are not prime, so it returns 0.
• It then iterates from i = 2 up to the square root of n (i * i <= n). This optimization is based on the fact that if a number n has a divisor greater than its square root, it must also have a divisor smaller than its square root.
• If n is divisible by any i in this loop (n % i == 0), then n is not prime, and the function returns 0.
• If the loop completes without finding any divisors, n is prime, and the function returns 1.

1. main Function:

• It prompts the user to enter a positive integer and stores it in the num variable.
• Edge Case Handling: It checks if num is less than 4. Since the smallest sum of two primes is 2 + 2 = 4, any number less than 4 cannot be expressed as the sum of two primes.
• A found flag is initialized to 0.
• The program then enters a for loop, iterating with i from 2 up to num / 2.
• Inside the loop, it calls the isPrime function for both i and num - i.
• If both i and num - i are prime, it prints the successful expression, sets found to 1, and breaks the loop since we only need to find one such pair.
• After the loop, if the found flag is still 0, it means no such prime pair was found, and an appropriate message is printed.

Conclusion

Determining if a number can be expressed as the sum of two prime numbers is a good exercise in applying fundamental programming concepts and number theory. By breaking down the problem into a reusable primality test function and an iterative checking mechanism, we can efficiently solve this challenge. The C program demonstrates a clear and effective method to approach such problems.

Summary

Here are the key takeaways from this article:

• The problem involves checking if an input number can be represented as prime1 + prime2.
• A helper function, isPrime(), is crucial for efficiently determining if a number is prime by checking divisibility up to its square root.
• The main logic iterates through possible first prime candidates (i) from 2 up to num / 2.
• For each i, both i and num - i are tested for primality.
• The program handles edge cases, such as numbers too small to be a sum of two primes.
• This approach provides a clear, structured way to solve problems involving number properties and iterative checks.