Check if a number exists having exactly N factors and K prime factors | C ++ program to check if it is possible to make a number having total N factors and K prime factors ; Function to compute the number of factors of the given number ; Vector to store the prime factors ; While there are no two multiples in the number , divide it by 2 ; If the size is already greater than K , then return true ; Computing the remaining divisors of the number ; If n is divisible by i , then it is a divisor ; If the size is already greater than K , then return true ; If the size is already greater than K , then return true ; If none of the above conditions satisfies , then return false ; Function to check if it is possible to make a number having total N factors and K prime factors ; If total divisors are less than the number of prime divisors , then print No ; Find the number of factors of n ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool factors ( int n , int k ) { vector < int > v ; while ( n % 2 == 0 ) { v . push_back ( 2 ) ; n /= 2 ; } if ( v . size ( ) >= k ) return true ; for ( int i = 3 ; i * i <= n ; i += 2 ) { while ( n % i == 0 ) { n = n / i ; v . push_back ( i ) ; } if ( v . size ( ) >= k ) return true ; } if ( n > 2 ) v . push_back ( n ) ; if ( v . size ( ) >= k ) return true ; return false ; } void operation ( int n , int k ) { bool answered = false ; if ( n < k ) { answered = true ; cout << " No " << " STRNEWLINE " ; } bool ok = factors ( n , k ) ; if ( ! ok && ! answered ) { answered = true ; cout << " No " << " STRNEWLINE " ; } if ( ok && ! answered ) cout << " Yes " << " STRNEWLINE " ; } int main ( ) { int n = 4 ; int k = 2 ; operation ( n , k ) ; return 0 ; }