C Program to Check Whether a Number Can Be Expressed as Sum of Two Prime Numbers

by

Checking if a number can be expressed as the sum of two prime numbers is an interesting problem that involves both number theory and algorithmic thinking. This article will explore C Program to Check Whether a Number Can Be Expressed as Sum of Two Prime Numbers, complete with examples, explanations, and outputs.

Prerequisites

Before diving into the examples, you should be familiar with:

  • Basic C syntax and structure.
  • Functions and loops in C.
  • Basic understanding of prime numbers.

Understanding the Problem

The problem requires us to determine whether a given number can be expressed as the sum of two prime numbers. For example, the number 34 can be expressed as the sum of two primes: 3 and 31.

Example 1: Basic Approach

1.1 Explanation

In this example, we will check if a number can be expressed as the sum of two primes by iterating through all pairs of numbers less than the given number. For each pair, we will check if both numbers are prime.

1.2 Program: Basic Approach

C
#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num);

int main() {
    int num, i;
    bool flag = false;

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

    for (i = 2; i <= num/2; ++i) {
        if (isPrime(i) && isPrime(num - i)) {
            printf("%d can be expressed as the sum of %d and %d.\n", num, i, num - i);
            flag = true;
        }
    }

    if (!flag)
        printf("%d cannot be expressed as the sum of two prime numbers.\n", num);

    return 0;
}

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

1.3 Output

C
Enter a positive integer: 34
34 can be expressed as the sum of 3 and 31.
34 can be expressed as the sum of 5 and 29.
34 can be expressed as the sum of 11 and 23.
34 can be expressed as the sum of 17 and 17.

Example 2: Optimized Approach Using a Sieve

2.1 Explanation

This example optimizes the previous approach by using the Sieve of Eratosthenes to precompute prime numbers up to the given number. This reduces the time complexity of checking if a number is prime.

2.2 Program: Optimized Approach

C
#include <stdio.h>
#include <stdbool.h>

void sieveOfEratosthenes(int n, bool prime[]);

int main() {
    int num, i;
    bool flag = false;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    bool prime[num+1];
    sieveOfEratosthenes(num, prime);

    for (i = 2; i <= num/2; ++i) {
        if (prime[i] && prime[num - i]) {
            printf("%d can be expressed as the sum of %d and %d.\n", num, i, num - i);
            flag = true;
        }
    }

    if (!flag)
        printf("%d cannot be expressed as the sum of two prime numbers.\n", num);

    return 0;
}

void sieveOfEratosthenes(int n, bool prime[]) {
    for (int i = 0; i <= n; i++)
        prime[i] = true;

    prime[0] = prime[1] = false;

    for (int p = 2; p*p <= n; p++) {
        if (prime[p]) {
            for (int i = p*p; i <= n; i += p)
                prime[i] = false;
        }
    }
}

2.3 Output

C
Enter a positive integer: 34
34 can be expressed as the sum of 3 and 31.
34 can be expressed as the sum of 5 and 29.
34 can be expressed as the sum of 11 and 23.
34 can be expressed as the sum of 17 and 17.

Example 3: Using a Separate Function to Check Pairs

3.1 Explanation

In this example, we will modularize the code further by creating a separate function to check if a number can be expressed as the sum of two primes. This function will use a helper function for prime checking.

3.2 Program: Separate Function for Checking Pairs

C
#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num);
bool canBeExpressedAsSumOfTwoPrimes(int num);

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

    if (canBeExpressedAsSumOfTwoPrimes(num))
        printf("%d can be expressed as the sum of two prime numbers.\n", num);
    else
        printf("%d cannot be expressed as the sum of two prime numbers.\n", num);

    return 0;
}

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

bool canBeExpressedAsSumOfTwoPrimes(int num) {
    for (int i = 2; i <= num/2; ++i) {
        if (isPrime(i) && isPrime(num - i)) {
            printf("%d can be expressed as the sum of %d and %d.\n", num, i, num - i);
            return true;
        }
    }
    return false;
}

3.3 Output

C
Enter a positive integer: 34
34 can be expressed as the sum of 3 and 31.
34 can be expressed as the sum of 5 and 29.
34 can be expressed as the sum of 11 and 23.
34 can be expressed as the sum of 17 and 17.
34 can be expressed as the sum of two prime numbers.

Conclusion

In this article, we explored different ways to check if a number can be expressed as the sum of two prime numbers using C programming. We covered three main examples:

  1. Basic Approach: Iterating through possible pairs and checking primality.
  2. Optimized Approach: Using the Sieve of Eratosthenes to precompute primes.
  3. Modular Approach: Using separate functions for clarity and modularity.

Each example demonstrated a different technique and provided outputs to illustrate the functionality. By understanding these examples, you can tackle similar problems and optimize your solutions for better performance.