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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int singlePrimeFactor ( int N ) { unordered_set < int > disPrimeFact ; for ( int i = 2 ; i * i <= N ; ++ i ) { while ( N % i == 0 ) { disPrimeFact . insert ( i ) ; N /= i ; } } if ( N != 1 ) { disPrimeFact . insert ( N ) ; } if ( disPrimeFact . size ( ) == 1 ) { return * disPrimeFact . begin ( ) ; } return -1 ; } int cntsingleFactorPair ( int arr [ ] , int N ) { int countOf1 = 0 ; unordered_map < int , int > mp ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) { countOf1 ++ ; continue ; } int factorValue = singlePrimeFactor ( arr [ i ] ) ; if ( factorValue == -1 ) { continue ; } else { mp [ factorValue ] ++ ; } } int res = 0 ; for ( auto it : mp ) { int X = it . second ; res += countOf1 * X + ( X * ( X - 1 ) ) / 2 ; } return res ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << cntsingleFactorPair ( arr , N ) ; return 0 ; }