C语言求2个数的最大公约数

迷南。 2024-04-08 12:40 81阅读 0赞

## 求2个数的最大公约数 ##

例如：40和20 的最大公约数为20

18和24 最大公约数为6

解释 最大公约数 取值范围： 在1~这两个数的最小值之间。

##### 代码1（效率低） #####

#include<stdio.h>
    int main()
    {
        
        int a=0,b=0;
        printf("请输入两个数字:>");
        scanf("%d %d",&a,&b);
        //将两个数字从大到小排序
        if(a<b)
        {
        
            int tmp=a;
            a=b;
            b=tmp;
        }
        int n=b;
        for(n=b;n>1;n--)
        {
        
            if ((a % n == 0) && (b % n == 0))
            {
        
                printf("最大公约数:>%d",n);
                break;
            }
        }
        if(n==1)
        {
        
            printf("最大公约数为 1");
        }
        return 0;
    }

##### 代码2(效率高) 辗转相除法 #####

解释辗转相除法：  
a % b =c;  
24 % 18 = 6;  
18 % 6 = 0;

**当最终的结果为0，那么上一个式子的模就是最大公约数**

#include<stdio.h>
    {
        
        int a=0,b=0;
        printf("请输入两个数字:>");
        scanf("%d %d",&a,&b);
        //辗转相除法不需要排序
        while(1)
        {
        
            int c=a%b;
            if(c==0)
            {
        
                printf("最大公约数:>%d",b);
                break;
            }
            a=b;
            b=c
        }
        return 0;
    
    }

运行结果  
![运行结果][944e57f332354160942195861ddc7905.png_pic_center]

**学的不是技术，更是梦想**

[944e57f332354160942195861ddc7905.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/11c0f05a52ca47bda6d7db3b74cccc2b.png