#Z0202208. 判断互质

判断互质

题目描述:

输入两个正整数m和n,判断m和n是否互质(即最大公约数为1),是则输出Yes,否则输出No。

输入格式:

输入两个整数m和n,中间用空格隔开。

输出格式:

如互质输出Yes,否则输出No。

样例输入:

36 56

样例输出:

No

提示:

1<=n,m<2^31

使用辗转相除法求出A、B的最大公约数(也就是最大公因数)

欧几里德算法又称​辗转相除法​,是指用于计算两个正整数a,b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。 image