Find prime factors of Array elements whose sum of exponents is divisible by K | C ++ program for the above approach ; To store the smallest prime factor till 10 ^ 5 ; Function to compute smallest prime factor array ; Initialize the spf array first element ; Marking smallest prime factor for every number to be itself ; Separately marking smallest prime factor for every even number as 2 ; Checking if i is prime ; Marking SPF for all numbers divisible by i ; Marking spf [ j ] if it is not previously marked ; Function that finds minimum operation ; Create a spf [ ] array ; Map created to store the unique prime numbers ; To store the result ; To store minimum operations ; To store every unique prime number ; Erase 1 as a key because it is not a prime number ; First Prime Number ; Frequency is divisible by K then insert primeNum in the result [ ] ; Print the elements if it exists ; Driver Code ; Given array arr [ ] ; Given K ; Function Call
#include <iostream> NEW_LINE #include <unordered_map> NEW_LINE #include <vector> NEW_LINE using namespace std ; int spf [ 10001 ] ; void spf_array ( int spf [ ] ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < 1000 ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < 1000 ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < 1000 ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < 1000 ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } void frequent_prime ( int arr [ ] , int N , int K ) { spf_array ( spf ) ; unordered_map < int , int > Hmap ; vector < int > result ; int i = 0 ; int c = 0 ; for ( i = 0 ; i < N ; i ++ ) { int x = arr [ i ] ; while ( x != 1 ) { Hmap [ spf [ x ] ] = Hmap [ spf [ x ] ] + 1 ; x = x / spf [ x ] ; } } Hmap . erase ( 1 ) ; for ( auto x : Hmap ) { int primeNum = x . first ; int frequency = x . second ; if ( frequency % K == 0 ) { result . push_back ( primeNum ) ; } } if ( result . size ( ) > 0 ) { for ( auto & it : result ) { cout << it << ' ▁ ' ; } } else { cout << " { } " ; } } int main ( ) { int arr [ ] = { 1 , 4 , 6 } ; int K = 1 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; frequent_prime ( arr , N , K ) ; }