Count pairs from an array with even product of count of distinct prime factors | C ++ implementation of 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000000 NEW_LINE void countOfPrimefactors ( vector < int > & CountDistinct ) { bool prime [ MAX + 1 ] ; for ( int i = 0 ; i <= MAX ; i ++ ) { CountDistinct [ i ] = 0 ; prime [ i ] = true ; } for ( long long int i = 2 ; i <= MAX ; i ++ ) { if ( prime [ i ] == true ) { CountDistinct [ i ] = 1 ; for ( long long int j = i * 2 ; j <= MAX ; j += i ) { CountDistinct [ j ] ++ ; prime [ j ] = false ; } } } } int CountEvenPair ( int A [ ] , int B [ ] , int N , int M ) { vector < int > countDistinct ( 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 ) { oddCount ++ ; } else { evenCount ++ ; } } for ( int i = 0 ; i < N ; i ++ ) { if ( countDistinct [ A [ i ] ] == 0 ) continue ; if ( countDistinct [ A [ i ] ] & 1 ) { evenPairs += ( evenCount ) ; } else { evenPairs += evenCount + oddCount ; } } return evenPairs ; } int main ( ) { int A [ ] = { 1 , 2 , 3 } ; int B [ ] = { 4 , 5 , 6 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int M = sizeof ( B ) / sizeof ( B [ 0 ] ) ; cout << CountEvenPair ( A , B , N , M ) ; return 0 ; }