python判断整数互质

Question

输入两个整数a，b，每行一个。
输出它们是否互质，如果互质的话，则输出：a and b are coprime，否则输出: a and b are not coprime。

Answer 1

辗转相除法

 
def gcd(m, n):
    return n if (m == 0) else gcd(n % m, m)
 
 
if __name__ == '__main__':
    m, n = map(int, input().split())
 
    print("%s\n", "{} and {} are coprime".format(m, n) if (gcd(m, n) == 1) else "{} and {} are not coprime".format(m, n))
 

望采纳

Answer 2

from math import gcd as bltin_gcd
a = int(input("请输入第一个数："))
b = int(input("请输入第二个数："))

def coprime(a, b):
    return bltin_gcd(a, b) == 1

if coprime(a, b) == True:
  print("{} and {} are coprime".format(a,b))
else:
  print("{} and {} are not coprime".format(a,b))

Answer 3

如果不引用类库，那就算最大公因数，辗转相除法
最大公因数是1就互质
while a%b:
a,b=b,a%b
最终b就是最大公因数