text: Find the number of pairs such that their gcd is equals to 1 | CPP 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100050 NEW_LINE int lpf [ N ] , mobius [ N ] ; void least_prime_factor ( ) { for ( int i = 2 ; i < N ; i ++ ) if ( ! lpf [ i ] ) for ( int j = i ; j < N ; j += i ) if ( ! lpf [ j ] ) lpf [ j ] = i ; } 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 ] ] ; } } } int gcd_pairs ( int a [ ] , int n ) { int maxi = 0 ; int fre [ N ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { fre [ a [ i ] ] ++ ; maxi = max ( a [ i ] , maxi ) ; } least_prime_factor ( ) ; Mobius ( ) ; int ans = 0 ; for ( int i = 1 ; i <= maxi ; i ++ ) { if ( ! mobius [ i ] ) continue ; int temp = 0 ; for ( int j = i ; j <= maxi ; j += i ) temp += fre [ j ] ; ans += temp * ( temp - 1 ) / 2 * mobius [ i ] ; } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << gcd_pairs ( a , n ) ; return 0 ; }