Find prime factors of Array elements whose sum of exponents is divisible by K | 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
spf = [ 0 for i in range ( 10001 ) ] NEW_LINE def spf_array ( spf ) : NEW_LINE INDENT spf [ 1 ] = 1 NEW_LINE for i in range ( 2 , 1000 , 1 ) : NEW_LINE INDENT spf [ i ] = i NEW_LINE DEDENT for i in range ( 4 , 1000 , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT i = 3 NEW_LINE while ( i * i < 1000 ) : NEW_LINE INDENT if ( spf [ i ] == i ) : NEW_LINE INDENT j = i * i NEW_LINE while ( j < 1000 ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT j += i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def frequent_prime ( arr , N , K ) : NEW_LINE INDENT spf_array ( spf ) NEW_LINE Hmap = { } NEW_LINE result = [ ] NEW_LINE i = 0 NEW_LINE c = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT x = arr [ i ] NEW_LINE while ( x != 1 ) : NEW_LINE INDENT Hmap [ spf [ x ] ] = Hmap . get ( spf [ x ] , 0 ) + 1 NEW_LINE x = x // spf [ x ] NEW_LINE DEDENT DEDENT if ( 1 in Hmap ) : NEW_LINE Hmap . pop ( 1 ) NEW_LINE for key , value in Hmap . items ( ) : NEW_LINE INDENT primeNum = key NEW_LINE frequency = value NEW_LINE if ( frequency % K == 0 ) : NEW_LINE INDENT result . append ( primeNum ) NEW_LINE DEDENT DEDENT result = result [ : : - 1 ] NEW_LINE if ( len ( result ) > 0 ) : NEW_LINE INDENT for it in result : NEW_LINE INDENT print ( it , end = " ▁ " ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " { } " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 4 , 6 ] NEW_LINE K = 1 NEW_LINE N = len ( arr ) NEW_LINE frequent_prime ( arr , N , K ) NEW_LINE DEDENT