Count pairs from an array with even product of count of distinct prime factors | js program for the above approach ; Function to calculate count of distinct prime factors of a number ; Sieve of Eratosthenes ; Function to count pairs with even product of distinct prime factors ; Stores count of distinct prime factors ; Stores the count of numbers with even prime factors in B [ ] ; Stores the count of numbers with odd prime factors in B [ ] ; Even Product Pairs ; Traverse the array B [ ] ; Since , product has to be positive i . e > 0 ; If count of prime factors is odd ; Increment oddCount by 1 ; Increment evenCount by 1 ; Since , product has to be positive i . e > 0 ; If count of prime factors is odd ; odd * even = even ; If count of prime factors is even ; even * odd = even even * even = even ; Driver Code
let countDistinct = Array ( 1000000 + 1 ) ; function countOfPrimefactors ( CountDistinct ) { let MAX = 1000000 ; let prime = Array ( MAX + 1 ) ; for ( let i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( let i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( let j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } } function CountEvenPair ( A , B , N , M ) { let MAX = 1000000 ; countOfPrimefactors ( countDistinct ) ; let evenCount = 0 ; let oddCount = 0 ; let evenPairs = 0 ; for ( let i = 0 ; i < M ; i ++ ) { if ( countDistinct [ B [ i ] ] == 0 ) continue ; if ( ( countDistinct [ B [ i ] ] & 1 ) != 0 ) { oddCount ++ ; } else { evenCount ++ ; } } for ( let i = 0 ; i < N ; i ++ ) { if ( countDistinct [ A [ i ] ] == 0 ) continue ; if ( ( countDistinct [ A [ i ] ] & 1 ) != 0 ) { evenPairs += ( evenCount ) ; } else { evenPairs += evenCount + oddCount ; } } return evenPairs ; } let A = [ 1 , 2 , 3 ] ; let B = [ 4 , 5 , 6 ] ; let N = A . length ; let M = B . length ; document . write ( CountEvenPair ( A , B , N , M ) ) ;