求两个数的最大公约数

求两个数的最大公约数

有两种方法     ：  1。先把x,y这两个数分解质因数
x=2^a·3^b·5^c… , y=2^m·3^n ·5^p…
最大公约数取x和y的公共的且次数最小的质因数想乘
最小公倍数取x和y的公共的且次数最大的质因数想乘,再乘以不公共的质因数
比如求12和30的最大公约数和最小公倍数:
12=2^2×3 , 30=2×3×5
最大公约数=2×3=6, 最小公倍数=2^2×3×5=60

    2.用辗转相除的数学思想。
main()
{ int m,n,r;
int min,max;
scanf("%d,%d",&m,&n);
max=m*n;
while（r=m％n）
｛m=n;
n=r;
｝
min=r;
max=max/r;

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息