猫史档案馆

初级：一个个枚举，直到正确答案出现。中级：由于最大公因数一定是任意一个数的因数，所以使用除法效率更高，平方根是为了再提升效率。如不使用平方根，则需要去掉枚举部分以提升效率。PS：此方法不稳定，建议实际不加枚举部分（平均时间较快，最坏情况较慢）高级：辗转相除法说明：A/B=C.....D，若设A和B的最大公因数为k，则A=a*k,B=b*k,D=a*k-b*C*k。（B<A)取公因式k得：D=(a-b*C)*k。可以知道，A，B，D，拥有相同的最大公因数k，又可知，若A/B=0，则B是A与B的最大公因数。所以，把小数B与余数D（D一定小于B)进行新一轮辗转相除法后可继续，直到余数=0，因为余数中一直有最大公因数k，所以，当余数=0时，小数即为当初两个数的最大公因数。积木：使用递归，终止条件为A/B=？....0。注意：一定把除数或被除数是0的情况排除！！！

囧仙_official

int _gcd(){

int gcd = __gcd(a[0],a[1])

for(int i = 2; i < n; i++){

gcd = __gcd(gcd,a[ii)

}

return gcd;

}

Regent

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 示例用法
num1 = 24
num2 = 36
result = gcd(num1, num2)
print("最大公因数为：", result)

猫史档案馆

求最大公因数

回复