Count of numbers upto M with GCD equals to K when paired with M | Function to calculate GCD using euler totient function ; Finding the prime factors of limit to calculate it 's  euler totient function ; Calculating the euler totient function of ( m / k ) ; Function print the count of numbers whose GCD with M equals to K ; GCD of m with any integer cannot be equal to k ; 0 and m itself will be the only valid integers ; Finding the number upto which coefficient of k can come ; Driver Code
function EulerTotientFunction ( limit ) { let copy = limit ; let primes = [ ] ; for ( let i = 2 ; i * i <= limit ; i ++ ) { if ( limit % i == 0 ) { while ( limit % i == 0 ) { limit /= i ; } primes . push ( i ) ; } } if ( limit >= 2 ) { primes . push ( limit ) ; } let ans = copy ; for ( let it in primes ) { ans = ( ans / primes [ it ] ) * ( primes [ it ] - 1 ) ; } return ans ; } function CountGCD ( m , k ) { if ( m % k != 0 ) { document . write ( 0 + " " ) ; return ; } if ( m == k ) { document . write ( 2 + " " ) ; return ; } let limit = Math . floor ( m / k ) ; let ans = EulerTotientFunction ( limit ) ; document . write ( ans + " " ) ; } let M = 9 ; let K = 1 ; CountGCD ( M , K ) ;