Count pairs whose product contains single distinct prime factor | 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
function singlePrimeFactor ( N ) { var disPrimeFact = { } ; for ( var i = 2 ; i * i <= N ; ++ i ) { while ( N % i === 0 ) { disPrimeFact [ i ] = 1 ; N = parseInt ( N / i ) ; } } if ( N !== 1 ) { disPrimeFact [ N ] = 1 ; } if ( Object . keys ( disPrimeFact ) . length === 1 ) { for ( const [ key , value ] of Object . entries ( disPrimeFact ) ) { return key ; } } return - 1 ; } function cntsingleFactorPair ( arr , N ) { var countOf1 = 0 ; var mp = { } ; for ( var i = 0 ; i < N ; i ++ ) { if ( arr [ i ] === 1 ) { countOf1 ++ ; continue ; } var factorValue = singlePrimeFactor ( arr [ i ] ) ; if ( factorValue === - 1 ) { continue ; } else { if ( mp . hasOwnProperty ( factorValue ) ) mp [ factorValue ] = mp [ factorValue ] + 1 ; else mp [ factorValue ] = 1 ; } } var res = 0 ; for ( const [ key , value ] of Object . entries ( mp ) ) { var X = value ; res = parseInt ( res + countOf1 * X + ( X * ( X - 1 ) ) / 2 ) ; } return res ; } var arr = [ 1 , 2 , 3 , 4 ] ; var N = arr . length ; document . write ( cntsingleFactorPair ( arr , N ) ) ;