Count pairs of natural numbers with GCD equal to given number | C ++ program to count pair in range of natural number having GCD equal to given number . ; Return the GCD of two numbers . ; Return the count of pairs having GCD equal to g . ; Setting the value of L , R . ; For each possible pair check if GCD is 1. ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { return b ? gcd ( b , a % b ) : a ; } int countGCD ( int L , int R , int g ) { L = ( L + g - 1 ) / g ; R = R / g ; int ans = 0 ; for ( int i = L ; i <= R ; i ++ ) for ( int j = L ; j <= R ; j ++ ) if ( gcd ( i , j ) == 1 ) ans ++ ; return ans ; } int main ( ) { int L = 1 , R = 11 , g = 5 ; cout << countGCD ( L , R , g ) << endl ; return 0 ; }