Count pairs from an array with even product of count of distinct prime factors | C # 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
using System ; public class GFG { static int MAX = 1000000 ; static void countOfPrimefactors ( int [ ] CountDistinct ) { bool [ ] prime = new bool [ MAX + 1 ] ; for ( int i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( int j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } } static int CountEvenPair ( int [ ] A , int [ ] B , int N , int M ) { int [ ] countDistinct = new int [ ( MAX + 1 ) ] ; countOfPrimefactors ( countDistinct ) ; int evenCount = 0 ; int oddCount = 0 ; int evenPairs = 0 ; for ( int i = 0 ; i < M ; i ++ ) { if ( countDistinct [ B [ i ] ] == 0 ) continue ; if ( ( countDistinct [ B [ i ] ] & 1 ) != 0 ) { oddCount ++ ; } else { evenCount ++ ; } } for ( int 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 ; } public static void Main ( string [ ] args ) { int [ ] A = { 1 , 2 , 3 } ; int [ ] B = { 4 , 5 , 6 } ; int N = A . Length ; int M = B . Length ; Console . WriteLine ( CountEvenPair ( A , B , N , M ) ) ; } }