C Program to Check Whether a Number can be Expressed as the Sum of Two Prime Numbers

In this tutorial, we’ll develop a C program to determine whether a given number can be expressed as the sum of two prime numbers. Prime numbers, being integers greater than 1 with no divisors other than 1 and the number itself, possess unique properties that make this problem interesting. We’ll design an algorithm to check if a given number can be represented as the sum of two prime numbers and implement it in C.

Algorithm to Check the Sum of Two Prime Numbers

C Program for Checking Sum of Two Prime Numbers

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

// Function to check if a number is prime
int isPrime(int num) {
    if (num < 2) {
        return 0; // Not prime
    }
    
    // Check for factors up to square root of num
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return 0; // Not prime
        }
    }
    return 1; // Prime
}

// Function to check if a number can be expressed as the sum of two primes
int canExpressAsSumOfTwoPrimes(int num) {
    // Check for each pair of numbers (i, num-i)
    for (int i = 2; i <= num / 2; i++) {
        if (isPrime(i) && isPrime(num - i)) {
            return 1; // It can be expressed as the sum of two primes
        }
    }
    return 0; // It cannot be expressed as the sum of two primes
}

int main() {
    int number;

    // Input from user
    printf("Enter a positive integer: ");
    scanf("%d", &number);

    // Check if the input is positive
    if (number <= 0) {
        printf("Please enter a positive integer.\n");
    } else {
        // Check if the number can be expressed as the sum of two primes
        if (canExpressAsSumOfTwoPrimes(number)) {
            printf("%d can be expressed as the sum of two prime numbers.\n", number);
        } else {
            printf("%d cannot be expressed as the sum of two prime numbers.\n", number);
        }
    }

    return 0;
}

Output Examples

Example 1: Expressible as the Sum of Two Primes

Enter a positive integer: 20
20 can be expressed as the sum of two prime numbers.

Example 3: Invalid Input

Enter a positive integer: -10
Please enter a positive integer.

Explanation

1. isPrime Function: The isPrime function checks if a given number is prime. It returns 1 for prime numbers and 0 for non-prime numbers.
2. canExpressAsSumOfTwoPrimes Function: This function checks if the input number can be expressed as the sum of two prime numbers. It iterates through pairs of numbers ($i,\text{num}-i$) and checks if both are prime using the isPrime function.
3. Main Function: The main function takes a positive integer input from the user and checks if it can be expressed as the sum of two prime numbers.

Conclusion

This C program efficiently determines whether a given positive integer can be expressed as the sum of two prime numbers. Understanding prime numbers and creating algorithms to work with them is fundamental in the field of computer science.

Feel free to experiment with different input values and observe how the program determines expressibility. If you have any questions or need further clarification, please don’t hesitate to ask!