普通方式求最大公约数

假设给定的两个整数m,n 如果要求最大公约数的话， 依次用m,n 除以从m,n中较小的数到1的这个范围的的整数， 最先能够同时整除的就是最大公约数

C代码实现如下：

int main(void)
{
    int m,n,s; //s 存储m,n中较小的值

    printf("Enter tow integers:");
    scanf("%d %d",&m,&n);

    if(m > n){
        s = n;
    }else{
        s = m;
    }

    while(s){
        if((m % s == 0) && (n % s ==0)){
            printf("The Greatest Common divison is:%d\n",s);
            break;
        }
        s--;
    }
}

当然也可以从1开始整除， 最后能同时被m,n整除的就是最大公约数， 基本差不多

Enclid算法

使用m,n 分别存储两个数。

如果n为0，那么停止操作，m的值就是最大公约数， 否则计算m除以n的余数， 把n保存到m中， 并把余数保存到n中。 重复上述过程， 每次都先判定n是否为0

C代码如下：

int main(void)
{
    int n,m,y;

    printf("Enter tow integers:");
    scanf("%d %d",&m,&n);

    do{
        y = m % n;
        m = n;
        n = y;
    }while(n != 0);

    printf("Greatest common divisor: %d\n",m);
}

后面一种方式很明显要比第一种方式效率高的多

仅记于此