Count pairs whose product contains single distinct prime factor | Java program to implement the above approach ; Function to find a single distinct prime factor of N ; Stores distinct prime factors of N ; Calculate prime factor of N ; Calculate distinct prime factor ; Insert i into disPrimeFact ; Update N ; If N is not equal to 1 ; Insert N into disPrimeFact ; If N contains a single distinct prime factor ; Return single distinct prime factor of N ; If N contains more than one distinct prime factor ; Function to count pairs in the array whose product contains only single distinct prime factor ; Stores count of 1 s in the array ; mp [ i ] : Stores count of array elements whose distinct prime factor is only i ; Traverse the array arr [ ] ; If current element is 1 ; Store distinct prime factor of arr [ i ] ; If arr [ i ] contains more than one prime factor ; If arr [ i ] contains a single prime factor ; Stores the count of pairs whose product of elements contains only a single distinct prime factor ; Traverse the map mp [ ] ; Stores count of array elements whose prime factor is ( it . first ) ; Update res ; Driver Code
import java . util . * ; class GFG { static int singlePrimeFactor ( int N ) { HashSet < Integer > disPrimeFact = new HashSet < > ( ) ; for ( int i = 2 ; i * i <= N ; ++ i ) { while ( N % i == 0 ) { disPrimeFact . add ( i ) ; N /= i ; } } if ( N != 1 ) { disPrimeFact . add ( N ) ; } if ( disPrimeFact . size ( ) == 1 ) { for ( int i : disPrimeFact ) return i ; } return - 1 ; } static int cntsingleFactorPair ( int arr [ ] , int N ) { int countOf1 = 0 ; HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) { countOf1 ++ ; continue ; } int factorValue = singlePrimeFactor ( arr [ i ] ) ; if ( factorValue == - 1 ) { continue ; } else { if ( mp . containsKey ( factorValue ) ) mp . put ( factorValue , mp . get ( factorValue ) + 1 ) ; else mp . put ( factorValue , 1 ) ; } } int res = 0 ; for ( Map . Entry < Integer , Integer > it : mp . entrySet ( ) ) { int X = it . getValue ( ) ; res += countOf1 * X + ( X * ( X - 1 ) ) / 2 ; } return res ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = arr . length ; System . out . print ( cntsingleFactorPair ( arr , N ) ) ; } }