C语言递归求最大公约数,最大公约数c++语言算法

辗转相除法

int gcd(int a,int b){if(a%b==0){printf("%d",b);return 0;}gcd(b,a%b);} #include <stdio.h>int main(){int a=24,b=10,i;if(a<b) //用辗转相除法要保证a>b{i=a;a=b;b=i;}gcd(a,b);}

如程序中的24和10
24(a)%10(b)=4
10(b)%4(a%b)=2
4(a%b)%2(b%(a%b))=0
最终最大公约数等于除数2。

我们也不难发现，辗转相除法是不断的套娃，a变成b，b又变成了a%b……所以我们可以用递归。