Find the number of pairs such that their gcd is equals to 1 | Javascript 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
var N = 100050 ; var lpf = Array ( N ) . fill ( 0 ) ; var mobius = Array ( N ) . fill ( 0 ) ; function least_prime_factor ( ) { for ( i = 2 ; i < N ; i ++ ) if ( lpf [ i ] == 0 ) for ( j = i ; j < N ; j += i ) if ( lpf [ j ] == 0 ) lpf [ j ] = i ; } function Mobius ( ) { for ( 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 ] ] ; } } } function gcd_pairs ( a , n ) { var maxi = 0 ; var fre = Array ( n + 1 ) . fill ( 0 ) ; for ( i = 0 ; i < n ; i ++ ) { fre [ a [ i ] ] ++ ; maxi = Math . max ( a [ i ] , maxi ) ; } least_prime_factor ( ) ; Mobius ( ) ; var ans = 0 ; for ( i = 1 ; i <= maxi ; i ++ ) { if ( mobius [ i ] == 0 ) continue ; var temp = 0 ; for ( j = i ; j <= maxi ; j += i ) temp = parseInt ( temp + fre [ j ] ) ; ans += parseInt ( temp * ( temp - 1 ) / 2 * mobius [ i ] ) ; } return ans ; } var a = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; var n = a . length ; document . write ( gcd_pairs ( a , n ) ) ;