Express Odd Number as Sum of Prime Numbers in C++

In this problem, we are given an odd number N. Our task is to express an odd number as the sum of prime numbers.

There can be at max three prime numbers while expressing the number.

Let’s take an example to understand the problem,

Input: N = 55

Output: 53 + 2

Solution Approach: 

The odd number can be represented as a sum of primes. Taking these primes into consideration we have three cases.

Case 1: If n is a prime number, it is represented as the sum of one prime number n.
Case 2: If (n - 2) is a prime number, it is represented as the sum of two prime numbers  n-2 and 2.

Case 3: ( n - 3 ) is an even number which can be represented as a sum of two prime numbers using Goldbach’s conjecture method in which we will check if a number A is prime and number {(n-3) - A } is also prime then print it.

Program to illustrate the working of our solution,

Example

Live Demo

#include <iostream>
using namespace std;

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

void primeAsSumofPrime(int n) {
   
   if (isPrime(n) )
      cout<<n;
   else if (isPrime(n - 2))
      cout<<"2 "<<"+ "<<(n - 2);
   else{
      cout<<"3 "<<"+ ";
      n -= 3;
      for (int i = 0; i < n; i++) {
         if (isPrime(i) && isPrime(n - i)) {
            cout<<i<<" + "<<(n - i);
            break;
         }
      }
   }
}

int main() {
   
   int n = 561;
   cout<<"The number "<<n<<" expressed as sum of primes is ";
   primeAsSumofPrime(n);
   return 0;
}

Output −

The number 561 expressed as sum of primes is 3 + 11 + 547