两数求最大公因数的方法(基于c语言编程)

一、枚举寻找法

1.简要阐述

        这个方法相对容易理解,并且方便记忆,但效率较低,因为毕竟这是暴力枚举。逻辑其实就是两个数字找出其中的较小数,从这个数依次减一,在两个数字同时整除一个数的时候,将其输出,这便是二者的最大公约数。

2.相关代码

         为方便得到结果,不妨直接取84和32。

#include <stdio.h>
int main(void)
{
    int a=84,b=32;
    int i;
    for(i=32;i>=1;i--)
    {
        if(a%i==0&&b%i==0)
        {
            printf("%d",i);
            break;
        }
    }
    return 0;
}

 二、辗转相除法

1.推导过程

        需求a,b两数的最大公因数,假设a大于b,因此便设a=b*m+r (r<b),m为a除以b所得商,r为对应余数,我们希望存在一个等式,使等式两边的数字呈整数倍的关系,因此希望找到一种迭代的方式来求解,这其实就是辗转相除法的主要核心方法,所以证明过程也要向这个方向上靠近。

        不妨令a与b的最大公因数为c,然后用p,q两整数表示出a和b,即a=p*c,b=q*c,然后将这两个关系式代入a=b*m+r,得p*c=q*m*c+r,移项得r=(p-qm)*c,观察比较二式b=q*c和r=(p-qm)*c可知,b和r的最大公约数C是大于等于c的,由式子a=b*m+r可知,a也有一个因数是C,已知a与b的最大公因数为c,因此c大于等于C,与“b和r的最大公约数C是大于等于c的”条件结合可得,c等于C,所以证明出了a,b与b,r的最大公因数是一样的。

        接下来其实就是辗转相除法的运用的理解,就是用除数代替被除数,余数代替除数,以此为迭代公式进行运算,直至运算后余数为0,此时的除数就是要求的最大公因数。

        我们可以用一个流程图更为直观的看出迭代过程。

        原来找到了一个不太正确的图更能说明辗转相除法的优势,就是不用像第一个方法去找哪个数小,在迭代过程中这一步可以自然地去实现。 

2.相关代码

#include <stdio.h>
int main(void)
{
    int a,b,r;
    scanf("%d%d",&a,&b);
    r=a%b;
    while(r!=0)
    {
        r = a%b;
        a = b;
        b = r;
    }
    printf("%d\n",a);
    return 0;
}

        因为一开始写这个代码就是根据之前推导过程写的,因此一开始我直接输出的是b,所以想再简单说明一下,while循环结束的标志是r变为0,但结束的前一个循环运算已经是a,b可以整除了,即r=0,该次循环中将b,即最大公约数的值赋给了a,r的0值赋给了下一个状态下的b,但我们其实要的应该是a,将其输出就可以了。