C Program to Check Whether a Number Can Be Express as Sum of Two Prime Numbers
Prime numbers are numbers that have only 2 factors, 1 and themselves. For example, 2, 3, 5, 7, 11, etc are some of the first prime numbers. Here we will see whether a number can be expressed as the sum of two prime numbers using a C program.
Example
Input: 7
Output: Yes
Explanation: 7 can be expressed as sum of 2 and 5 which are primeInput: 11
Output: No
Explanation: There are no two prime numbers such that their sum is 11
Approach
The idea is to loop from 2 to N and check if N-i and i are prime Below is the C program to check whether a number can be expressed as the sum of two prime numbers:
// C program to check whether a
// number can be expressed as sum
// of two prime numbers
#include <stdio.h>
// Function to check prime number
int isPrime(int n)
{
int i, isPrime = 1;
// 0 and 1 are not prime numbers
if (n == 0 || n == 1) {
isPrime = 0;
}
else {
for (i = 2; i <= n / 2; ++i) {
if (n % i == 0) {
isPrime = 0;
break;
}
}
}
return isPrime;
}
// Driver code
int main()
{
int n = 7, i, flag = 0;
for (i = 2; i <= n / 2; ++i) {
// condition for i to be a
// prime number
if (isPrime(i) == 1) {
// condition for n-i to
// be a prime number
if (isPrime(n - i) == 1) {
printf("Yes\n");
return 0;
}
}
}
printf("No\n");
return 0;
}
Output
Yes
The complexity of the method above
Time Complexity: O(N2)
Auxiliary Space: O(1)