Find the number of pairs such that their gcd is equals to 1 | Java 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
class GFG { static int N = 100050 ; static int [ ] lpf = new int [ N ] ; static int [ ] mobius = new int [ N ] ; static void least_prime_factor ( ) { for ( int i = 2 ; i < N ; i ++ ) if ( lpf [ i ] == 0 ) for ( int j = i ; j < N ; j += i ) if ( lpf [ j ] == 0 ) lpf [ j ] = i ; } static void Mobius ( ) { for ( int i = 1 ; i < N ; i ++ ) { if ( i == 1 ) mobius [ i ] = 1 ; else { if ( lpf [ i / lpf [ i ] ] == lpf [ i ] ) mobius [ i ] = 0 ; else mobius [ i ] = - 1 * mobius [ i / lpf [ i ] ] ; } } } static int gcd_pairs ( int a [ ] , int n ) { int maxi = 0 ; int [ ] fre = new int [ N ] ; for ( int i = 0 ; i < n ; i ++ ) { fre [ a [ i ] ] ++ ; maxi = Math . max ( a [ i ] , maxi ) ; } least_prime_factor ( ) ; Mobius ( ) ; int ans = 0 ; for ( int i = 1 ; i <= maxi ; i ++ ) { if ( mobius [ i ] == 0 ) continue ; int temp = 0 ; for ( int j = i ; j <= maxi ; j += i ) temp += fre [ j ] ; ans += temp * ( temp - 1 ) / 2 * mobius [ i ] ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int n = a . length ; System . out . print ( gcd_pairs ( a , n ) ) ; } }