图解
“面积法”求最大公约数
上图所示的是一个 22 * 8 的长方形。
这个长方形可分为两个8 * 8的正方形和一个 8 * 6 的长方形，将这个 8 * 6 的长方形继续分出正方形，直到全部都是正方形为止，此时最小的正方形的边长就是 22 与 8 的最大公约数。
代码分析
#include<stdio.h>
#include<stdlib.h>
//求出最大公约数gcd(greatest common divisor)
int gcdf(int length, int width)
{
return ((width == 0) ? length : gcdf(width, length % width));
}
//判断大小并直接返回最大公约数
int gcd(int length, int width)
{
return ((length > width) ? gcdf(length, width) : gcdf(width, length));
}
int main()
{
int a, b;
puts("Please enter two numbers:");
printf("Number1:"); scanf("%d", &a);
printf("Number2:"); scanf("%d", &b);
printf("The greatest common divisor is %d .\n", gcd(a, b));
system("pause");
return (0);
}