Check if each element of the given array is the product of exactly K prime numbers | C ++ program to check if each element of the given array is a product of exactly K prime factors ; initialise the global sieve array ; Function to generate Sieve ; NOTE : k value is necessarily more than 1 hence , 0 , 1 and any prime number cannot be represented as product of two or more prime numbers ; Function to check if each number of array satisfies the given condition ; Driver Code ; first construct the sieve
#include <iostream> NEW_LINE #define MAX  1000000 NEW_LINE using namespace std ; int Sieve [ MAX ] = { 0 } ; void constructSieve ( ) { for ( int i = 2 ; i <= MAX ; i ++ ) { if ( Sieve [ i ] == 0 ) { for ( int j = 2 * i ; j <= MAX ; j += i ) { int temp = j ; while ( temp > 1 && temp % i == 0 ) { Sieve [ j ] ++ ; temp = temp / i ; } } } } } void checkElements ( int A [ ] , int n , int k ) { for ( int i = 0 ; i < n ; i ++ ) { if ( Sieve [ A [ i ] ] == k ) { cout << " YES STRNEWLINE " ; } else { cout << " NO STRNEWLINE " ; } } } int main ( ) { constructSieve ( ) ; int k = 3 ; int A [ ] = { 12 , 36 , 42 , 72 } ; int n = sizeof ( A ) / sizeof ( int ) ; checkElements ( A , n , k ) ; return 0 ; }