Maximum count of pairwise co | Function to find the gcd of two numbers ; Function to of pairwise co - prime and common divisors of two numbers ; Initialize answer with 1 , to include 1 in the count ; Count of primes of gcd ( N , M ) ; Finding prime factors of gcd ; Increment count if it is divisible by i ; Return the total count ; Function Call for each pair to calculate the count of pairwise co - prime divisors ; Driver Code ; Given array of pairs ; Function Call
def gcd ( x , y ) : NEW_LINE INDENT if ( x % y == 0 ) : NEW_LINE INDENT return y NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( y , x % y ) NEW_LINE DEDENT DEDENT def countPairwiseCoprime ( N , M ) : NEW_LINE INDENT answer = 1 NEW_LINE g = gcd ( N , M ) NEW_LINE temp = g NEW_LINE for i in range ( 2 , g + 1 ) : NEW_LINE INDENT if i * i > g : NEW_LINE INDENT break NEW_LINE DEDENT if ( temp % i == 0 ) : NEW_LINE INDENT answer += 1 NEW_LINE while ( temp % i == 0 ) : NEW_LINE INDENT temp //= i NEW_LINE DEDENT DEDENT DEDENT if ( temp != 1 ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT return answer NEW_LINE DEDENT def countCoprimePair ( arr , N ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT print ( countPairwiseCoprime ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 12 , 18 ] , [ 420 , 660 ] ] NEW_LINE N = len ( arr ) NEW_LINE countCoprimePair ( arr , N ) NEW_LINE DEDENT