Split N as the sum of K numbers satisfying the given conditions | C ++ Program to implement the above approach ; Vector to store prime numbers ; Function to generate prime numbers using SieveOfEratosthenes ; Boolean array to store primes ; If p is a prime ; Mark all its multiples as non - prime ; Print all prime numbers ; Function to generate n as the sum of k numbers where atleast K - 1 are distinct and are product of 2 primes ; Stores the product of every pair of prime number ; Sort the products ; If sum exceeds n ; Otherwise , print the k required numbers ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > primes ; void SieveOfEratosthenes ( ) { bool prime [ 10005 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= 1000 ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= 1000 ; i += p ) prime [ i ] = false ; } } for ( int p = 2 ; p <= 1000 ; p ++ ) if ( prime [ p ] ) primes . push_back ( p ) ; } void generate ( int n , int k ) { vector < long long > prod ; SieveOfEratosthenes ( ) ; int l = primes . size ( ) ; for ( int i = 0 ; i < l ; i ++ ) { for ( int j = i + 1 ; j < l ; j ++ ) { if ( primes [ i ] * primes [ j ] > 0 ) prod . push_back ( primes [ i ] * primes [ j ] ) ; } } sort ( prod . begin ( ) , prod . end ( ) ) ; int sum = 0 ; for ( int i = 0 ; i < k - 1 ; i ++ ) sum += prod [ i ] ; if ( sum > n ) cout << " - 1" ; else { for ( int i = 0 ; i < k - 1 ; i ++ ) { cout << prod [ i ] << " , ▁ " ; } cout << n - sum << " STRNEWLINE " ; } } int main ( ) { int n = 52 , k = 5 ; generate ( n , k ) ; return 0 ; }