Count pairs whose product contains single distinct prime factor | C # 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
using System ; using System . Collections . Generic ; class GFG { static int singlePrimeFactor ( int N ) { HashSet < int > disPrimeFact = new HashSet < int > ( ) ; 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 . Count == 1 ) { foreach ( int i in disPrimeFact ) return i ; } return - 1 ; } static int cntsingleFactorPair ( int [ ] arr , int N ) { int countOf1 = 0 ; Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; 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 [ factorValue ] = mp [ factorValue ] + 1 ; else mp . Add ( factorValue , 1 ) ; } } int res = 0 ; foreach ( KeyValuePair < int , int > ele1 in mp ) { int X = ele1 . Value ; res += countOf1 * X + ( X * ( X - 1 ) ) / 2 ; } return res ; } public static void Main ( ) { int [ ] arr = { 1 , 2 , 3 , 4 } ; int N = arr . Length ; Console . WriteLine ( cntsingleFactorPair ( arr , N ) ) ; } }