Count all possible values of K less than Y such that GCD ( X , Y ) = GCD ( X + K , Y ) | Java program for the above approach ; Function to find the gcd of a and b ; Function to find the number of Ks ; Find gcd ; Calculating value of totient function for n ; Driver Code ; Given X and Y
import java . util . * ; class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static int calculateK ( int x , int y ) { int g = gcd ( x , y ) ; int n = y / g ; int res = n ; for ( int i = 2 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { res -= ( res / i ) ; while ( n % i == 0 ) n /= i ; } } if ( n != 1 ) res -= ( res / n ) ; return res ; } public static void main ( String [ ] args ) { int x = 3 , y = 15 ; System . out . print ( calculateK ( x , y ) + "NEW_LINE"); } }