Find if n can be written as product of k numbers | C ++ program to find if it is possible to write a number n as product of exactly k positive numbers greater than 1. ; Prints k factors of n if n can be written as multiple of k numbers . Else prints - 1. ; A vector to store all prime factors of n ; Insert all 2 's in vector ; n must be odd at this point So we skip one element ( i = i + 2 ) ; This is to handle when n > 2 and n is prime ; If size ( P ) < k , k factors are not possible ; printing first k - 1 factors ; calculating and printing product of rest of numbers ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void kFactors ( int n , int k ) { vector < int > P ; while ( n % 2 == 0 ) { P . push_back ( 2 ) ; n /= 2 ; } for ( int i = 3 ; i * i <= n ; i = i + 2 ) { while ( n % i == 0 ) { n = n / i ; P . push_back ( i ) ; } } if ( n > 2 ) P . push_back ( n ) ; if ( P . size ( ) < k ) { cout << " - 1" << endl ; return ; } for ( int i = 0 ; i < k - 1 ; i ++ ) cout << P [ i ] << " , ▁ " ; int product = 1 ; for ( int i = k - 1 ; i < P . size ( ) ; i ++ ) product = product * P [ i ] ; cout << product << endl ; } int main ( ) { int n = 54 , k = 3 ; kFactors ( n , k ) ; return 0 ; }