C Program to Check if a Number is Sum of Two Primes

Ever wondered if you can write a number as the sum of two prime numbers? It's a cool way to dive into arithmetic and prime properties. In this program, we’ll input a number and see if it adds up to two primes. For example, 20 equals 3 + 17, which are both prime.

Prerequisites for Checking Sum of Two Primes in C

Before writing this program, you'll need the following:

• Understanding of loops like for and while
• Knowledge of if-else conditions
• Familiarity with functions in C
• A C compiler such as GCC 9 or newer — or just run it in the EduSeekho online compiler
• The <stdio.h> library for input and output

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

Here's the C code that checks if a number can be expressed as a sum of two prime numbers:

#include <stdio.h>

int isPrime(int n) {/* Function to check if a number is prime */}
{
    if (n < 2) return 0;
    for (int i = 2; i*i <= n; ++i) {
        if (n % i == 0) return 0;
    }
    return 1;
}

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

    int found = 0;
    for (int i = 2; i <= n/2; ++i) {
        if (isPrime(i) && isPrime(n - i)) {
            printf("%d can be expressed as the sum of %d and %d which are prime numbers.\n", n, i, n-i);
            found = 1;
            break;
        }
    }
    if (!found) {
        printf("%d cannot be expressed as a sum of two prime numbers.\n", n);
    }
    return 0;
}

Output of the Sum of Two Primes Program

Let's see what the program prints when you enter a number like 20:

Enter a positive integer: 20
20 can be expressed as the sum of 3 and 17 which are prime numbers.

Algorithm to Check Sum of Two Primes in C

Checking if a number can be expressed as a sum of two prime numbers involves iterating through possible pairs and checking their primality. Here's how the algorithm works:

1. Read the number n from the user.
2. Check if n is less than or equal to 1. If true, it's not possible to express it as a sum of two primes.
3. If n is not prime, try finding two prime numbers p and q such that p + q = n.
4. Iterate i from 2 to n/2, and check if both i and n-i are primes.
5. If such a pair is found, print the pair p and q.
6. If no such pair is found, indicate that n cannot be expressed as a sum of two primes.

flowchart TD
  A([Start]) --> B[/Read number n/]
  B --> C{n <= 1?}
  C -->|Yes| D([End])
  C -->|No| E{Is n a prime number?}
  E -->|Yes| F([End])
  E -->|No| G[/Find two prime numbers p and q such that p + q = n/]
  G --> H{Found?}
  H -->|Yes| I([Success])
  H -->|No| J([Fail])

How the C Program to Check Sum of Two Primes Works

Let's break down exactly how this C program works line by line:

• The code includes #include <stdio.h> for input and output functions.
• The isPrime function checks if a given number is prime by attempting to divide it with numbers up to its square root.
• Inside main, we first print a prompt and read the user's input with scanf.
• A for loop iterates from 2 to n/2, checking pairs of numbers i and n-i for primality using the isPrime function.
• If a valid pair is found, it prints the result and uses break to exit the loop.
• If no valid pair is found, the program prints that the number cannot be expressed as a sum of two primes.
• Finally, the program returns 0, indicating successful execution.

Time and Space Complexity of the C Program to Check Sum of Two Primes

Let's analyze the time and space efficiency of this program.

Time Complexity: O(n √n). Here, n is the number input by the user, and √n is due to the primality test for each number up to n/2 in the worst case. If you enter 20, it checks up to 10 pairs at most.

Space Complexity: O(1). The program uses only a fixed set of variables like n, i, and found. These don't depend on the size of input.

Key takeaway: This program checks prime sums effectively by using number properties and simple loops.

FAQs About Checking Sum of Two Primes in C

Here are some common questions students ask:

Related Programs

If you found this program helpful, check out these related programs:

• C Program to Display Prime Numbers Between Two Intervals
• C Program to Check Armstrong Number
• C Program to Display Armstrong Number Between Two Intervals
• C Program to Display Factors of a Number
• C Program to Check Prime or Armstrong Number Using User-defined Function

Conclusion

Figuring out if a number’s a sum of two primes is a neat exercise in number theory. It really helps you get a better grasp of primes and loops in C. Try out more C programs with arithmetic and primes to sharpen your skills.

Practice more with C quizzes and run this program in the online compiler. Keep coding!