Find prime factors of Array elements whose sum of exponents is divisible by K | Java 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
import java . util . * ; class GFG { static int [ ] spf = new int [ 10001 ] ; static 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 ; } } } static void frequent_prime ( int arr [ ] , int N , int K ) { spf_array ( spf ) ; Map < Integer , Integer > Hmap = new TreeMap < > ( ) ; ArrayList < Integer > result = new ArrayList < > ( ) ; int i = 0 ; int c = 0 ; for ( i = 0 ; i < N ; i ++ ) { int x = arr [ i ] ; while ( x != 1 ) { Hmap . put ( spf [ x ] , Hmap . getOrDefault ( spf [ x ] , 0 ) + 1 ) ; x = x / spf [ x ] ; } } Hmap . remove ( 1 ) ; for ( Map . Entry < Integer , Integer > x : Hmap . entrySet ( ) ) { int primeNum = x . getKey ( ) ; int frequency = x . getValue ( ) ; if ( frequency % K == 0 ) { result . add ( primeNum ) ; } } if ( result . size ( ) > 0 ) { for ( Integer it : result ) { System . out . print ( it + " ▁ " ) ; } } else { System . out . print ( " { } " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 4 , 6 } ; int K = 1 ; int N = arr . length ; frequent_prime ( arr , N , K ) ; } }