最大公约数代码

欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
扩展欧几里得算法可用于RSA加密等领域。
https://baike.baidu.com/item/欧几里得算法/1647675#
https://blog.csdn.net/qinzaoxiaozhu/article/details/113917610

下为证明过程

流程图

伪代码实现欧几里得算法

read a
read b

while(a<b)
temp=a
a=b
b=temp

if(b=0)
print a
else
c=a%b

while(c=0)
a=b
b=c

while(c!=0)
print b

手动验算