Represent a number as the sum of the largest possible number of prime numbers in C++

Discuss a problem, for example, given a number N, we need to split the number into the largest prime number and

Input: N = 7
Output: 2 2 3
Explanation: 7 can be represented as the sum of two 2’s and a 3 which are the maximum possible prime numbers.

Input : N = 17
Output: 2 2 2 2 2 2 2 3

Solution method

To represent a number in terms of primes, we can subtract a prime number from N and then check the difference in the prime numbers. If the difference is a prime number, then we can express N as the sum of two prime numbers.

But here we have to find the maximum number of prime numbers and for this we should take the minimum prime numbers i.e. 2 and 3. We can make any number from 2 and 3.

• Check the even number; if it is an even number, it can be composed of the sum of (N/2) 2.

• can be composed of a three sum [ (N-3) / 2] or 2 if it is an odd number.

• In this way, we can use the sum of the largest prime numbers to represent N.

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
   int N = 7;
   // checking if N is odd,
   // If yes, then print 3
   // and subtract 3 from N.
   if (N & 1 == 1) {
      cout << "3 +";
      N -= 3;
   }
   // // keep subtracting and printing 2
   // until N is becomes 0.
   while (N!=2) {
      cout << " 2 +";
      N -= 2;
   }
   cout << " 2";
   return 0;
}

Output

3 + 2 + 2

Conclusion

In this tutorial we discussed about representing a number as a maximum number of primes Sum. We discussed a simple way to solve this problem, which is to express the number as the sum of 2 and 3. We also discussed a C program to solve this problem and we can implement it using programming languages ​​like C, Java, Python etc. We hope you found this tutorial helpful.

The above is the detailed content of Represent a number as the sum of the largest possible number of prime numbers in C++. For more information, please follow other related articles on the PHP Chinese website!