Find the number of pairs such that their gcd is equals to 1 | Python3 program to find the number of pairs such that gcd equals to 1 ; Function to calculate least prime factor of each number ; If it is a prime number ; For all multiples which are not visited yet . ; Function to find the value of Mobius function for all the numbers from 1 to n ; If number is one ; If number has a squared prime factor ; Multiply - 1 with the previous number ; Function to find the number of pairs such that gcd equals to 1 ; To store maximum number ; To store frequency of each number ; Find frequency and maximum number ; To store number of pairs with gcd equals to 1 ; Traverse through the all possible elements ; Return the number of pairs ; Driver code ; Function call
N = 100050 NEW_LINE lpf = [ 0 for i in range ( N ) ] NEW_LINE mobius = [ 0 for i in range ( N ) ] NEW_LINE def least_prime_factor ( ) : NEW_LINE INDENT for i in range ( 2 , N ) : NEW_LINE INDENT if ( lpf [ i ] == 0 ) : NEW_LINE INDENT for j in range ( i , N , i ) : NEW_LINE INDENT if ( lpf [ j ] == 0 ) : NEW_LINE INDENT lpf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def Mobius ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT if ( i == 1 ) : NEW_LINE INDENT mobius [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( lpf [ ( i // lpf [ i ] ) ] == lpf [ i ] ) : NEW_LINE INDENT mobius [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT mobius [ i ] = - 1 * mobius [ i // lpf [ i ] ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def gcd_pairs ( a , n ) : NEW_LINE INDENT maxi = 0 NEW_LINE fre = [ 0 for i in range ( N ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT fre [ a [ i ] ] += 1 NEW_LINE maxi = max ( a [ i ] , maxi ) NEW_LINE DEDENT least_prime_factor ( ) NEW_LINE Mobius ( ) NEW_LINE ans = 0 NEW_LINE for i in range ( 1 , maxi + 1 ) : NEW_LINE INDENT if ( mobius [ i ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT temp = 0 NEW_LINE for j in range ( i , maxi + 1 , i ) : NEW_LINE INDENT temp += fre [ j ] NEW_LINE DEDENT ans += temp * ( temp - 1 ) // 2 * mobius [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( a ) NEW_LINE print ( gcd_pairs ( a , n ) ) NEW_LINE