图解

“面积法”求最大公约数

上图所示的是一个 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);
}