Check whether a number can be expressed as a sum of two prime numbers

Program to check whether a number can be expressed as a sum of two prime numbers is discussed here. Given a positive integer N. The task is to check if the number N can be represented as a sum of two prime numbers.

For example, the number 34 is given as input.

  • 34 = 3 + 31
  • 34 = 5 + 29
  • 34 = 11 + 23
  • 34 = 17 + 17

Algorithm to check whether a number can be expressed as a sum of two prime numbers

  • Input the number to be checked.
  • Repeat from i = 2 to (num/2).
  • Check if (i) is a prime number.
  • If i is prime, check if (n – i) is a prime number.
  • If both (i)and (n – i) are primes, then the given number can be represented as the sum of primes i and (n – i).

Program to check whether a number can be expressed as a sum of two prime numbers

// C program to check whether a number can be expressed as a sum of two prime numbers

#include
int sum_of_two_primes(int n);
int main()
{
int n, i;

printf(“Enter the number: “);
scanf(“%d”, &n);
int flag = 0;
for(i = 2; i <= n/2; ++i)
{

// Condition for i to be prime
if (sum_of_two_primes(i) == 1)
{


if (sum_of_two_primes(n-i) == 1)
{
printf(“\n%d can be expressed as the sum of %d and %d\n\n”, n, i, n – i);
flag = 1;
}

}
}

if (flag == 0)
printf(“%d cannot be expressed as the sum of two prime numbers\n”, n);

return 0;
}

int sum_of_two_primes(int n)
{
int i, isPrime = 1;

for(i = 2; i <= n/2; ++i)
{
if(n % i == 0)
{
isPrime = 0;
break;
}
}

return isPrime;
}

// C++ program to check whether a number can be expressed as a sum of two prime numbers

#include
using namespace std;

int sum_of_two_primes(int n);
int main()
{
int n, i;

cout << “Enter the number: “;
cin >> n;
int flag = 0;
for(i = 2; i <= n/2; ++i)
{

// condition for i to be prime
if (sum_of_two_primes(i) == 1)
{


if (sum_of_two_primes(n-i) == 1)
{
cout << n << ” can be expressed as the sum of ” << i << ” and ” << n-i << endl;
flag = 1;
}

}
}

if (flag == 0)
cout << n << ” cannot be expressed as the sum of two prime numbers\n”;

return 0;
}

int sum_of_two_primes(int n)
{
int i, isPrime = 1;

for(i = 2; i <= n/2; ++i)
{
if(n % i == 0)
{
isPrime = 0;
break;
}
}

return isPrime;
}

// Java program to check whether a number can be expressed as a sum of two prime numbers

import java.util.*;
public class sum_of_primes {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print(“Enter a number: “);
int number = sc.nextInt();
boolean flag = false;
for (int i = 2; i <= number / 2; ++i) {

if (sum_of_primes(i)) {

if (sum_of_primes(number – i)) {

System.out.printf(“%d can be expressed as the sum of %d and %d\n”, number, i, number – i);
flag = true;
}

}
}

if (!flag)
System.out.println(number + ” cannot be expressed as the sum of two prime numbers.”);
}

static boolean sum_of_primes(int num) {
boolean isPrime = true;

for (int i = 2; i <= num / 2; ++i) {
if (num % i == 0) {
isPrime = false;
break;
}
}

return isPrime;
}
}

# Python program to check whether a number can be expressed as a sum of two prime numbers

def sum_of_primes(num):
isPrime = 1
for i in range (2,int(num/2),1):
if(num % i == 0):
isPrime = 0
break
return isPrime
num = int(input(“Enter a number : “))
flag = 0;
i = 2
for i in range (2,int(num/2),1):
if(sum_of_primes(i) == 1):
if(sum_of_primes(num-i) == 1):
print(num,”can be expressed as the sum of”,i,”and”,num-i)
flag = 1;
if (flag == 0):
print(n,”cannot be expressed as the sum of two prime numbers”)

Output:

check whether a number can be expressed as a sum of two prime numbers