Home » C++ programs

C++ program to find largest list of prime numbers

Here, we are going to learn how to find the largest list of prime numbers?
Submitted by Debasis Jana, on January 28, 2019

Problem statement:

You are given a number N, you have to find the largest list of prime numbers that will give N after summation of the list.

Example:

    Sample Input:
    7
    2

    Sample Output:
    2  2  3
    2

Explanation:

    7 can be expressed as summation of 2+2+3
    2 can be expressed as summation of 2

Basic Idea:

A number can be expressed as summation of longest list of prime numbers only when it is expressed only with 2 and 3.

Algorithm:

prime_List(N)
    1.  if(N%2)==0
    2.  Express it as summation of (N/2) number of 2
    3.  Else if(N%2)!=0
        //So that N can be even, for example N=19, so now N=19-3=16
    4.  Set N=N-3   
    5.  Print (N/2) numbers of 2
    6.  Print 3
    7.  END of Program.

C++ program

#include<bits/stdc++.h>
using namespace std;

int list_prime(int n)
{	
	int i;
	if(n<2)
	{
		cout<<"Summation not possible\n";
	}
	//if n can be divided by 2, then we can express 
	//it as summation of 2 only
	else if(n%2==0)			
	{
		for(i=1;i<=n/2;i++)
		{
			cout<<2<<" ";
		}
	}
	else
	{
		//making the number even
		n=n-3;
		//n can be divided by 2 now
		for(i=1;i<=n/2;i++)	
			cout<<2<<" ";
		//add 3, and the summation will be now n
		cout<<3<<" ";
	}
}

int main()
{
	int i,n;
	
	cin>>n;
	
	list_prime(n);

	return 0;
}

Output

7
2 2 3