Count of numbers upto M with GCD equals to K when paired with M | Java program to Count of numbers between 0 to M which have GCD with M equals to K . ; 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
import java . util . * ; class GFG { static int EulerTotientFunction ( int limit ) { int copy = limit ; Vector < Integer > primes = new Vector < Integer > ( ) ; for ( int i = 2 ; i * i <= limit ; i ++ ) { if ( limit % i == 0 ) { while ( limit % i == 0 ) { limit /= i ; } primes . add ( i ) ; } } if ( limit >= 2 ) { primes . add ( limit ) ; } int ans = copy ; for ( int it : primes ) { ans = ( ans / it ) * ( it - 1 ) ; } return ans ; } static void CountGCD ( int m , int k ) { if ( m % k != 0 ) { System . out . print ( 0 + "NEW_LINE"); return ; } if ( m == k ) { System . out . print ( 2 + "NEW_LINE"); return ; } int limit = m / k ; int ans = EulerTotientFunction ( limit ) ; System . out . print ( ans + "NEW_LINE"); } public static void main ( String [ ] args ) { int M = 9 ; int K = 1 ; CountGCD ( M , K ) ; } }