Count all possible values of K less than Y such that GCD ( X , Y ) = GCD ( X + K , Y ) | 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
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def calculateK ( x , y ) : NEW_LINE INDENT g = gcd ( x , y ) NEW_LINE n = y // g NEW_LINE res = n NEW_LINE i = 2 NEW_LINE while i * i <= n : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT res -= ( res // i ) NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT n //= i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT if ( n != 1 ) : NEW_LINE INDENT res -= ( res // n ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT x = 3 NEW_LINE y = 15 NEW_LINE print ( calculateK ( x , y ) ) NEW_LINE DEDENT