Example: Check if Number is Sum of Two Primes in C

// 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;
}