Count pairs of natural numbers with 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. ; Driver Code
< ? php function gcd ( $ a , $ b ) { return $ b ? gcd ( $ b , $ a % $ b ) : $ a ; } function countGCD ( $ L , $ R , $ g ) { $ L = ( $ L + $ g - 1 ) / $ g ; $ R = $ R / $ g ; $ ans = 0 ; for ( $ i = $ L ; $ i <= $ R ; $ i ++ ) for ( $ j = $ L ; $ j <= $ R ; $ j ++ ) if ( gcd ( $ i , $ j ) == 1 ) $ ans ++ ; return $ ans ; } $ L = 1 ; $ R = 11 ; $ g = 5 ; echo countGCD ( $ L , $ R , $ g ) ; ? >