输入两个正整数，输出其最大公约数。

╰+攻爆jí腚メ 2023-07-03 10:59 8阅读 0赞

## 辗转相除法 ##

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

# include<stdio.h>
    int main()
    { 
    	int num1,num2,t=1;
    	scanf("%d %d",&num1,&num2);
    	while(t)         //辗转相除法
    	{ 
    		t=num1%num2;
    		num1=num2;
    		num2=t;
    	 } 
    	 printf("%d",num1);
    	 return 0;
    }

对于求最大公约数还可以用 ：更相减损术。但要考虑其num1与num2的大小。

## 更相减损术 ##

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。  
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。  
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。  
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

# include<stdio.h>
    # include<math.h>
    int main()
    { 
    	int num1,num2,count=0;
    	scanf("%d %d",&num1,&num2);
        if((num1%2==0)&&(num2%2==0))
        { 
        	num1/=2;
        	num2/=2;
        	count++;
    	}     //减少运算量
    	while(num1!=num2)  //更相减损术
    	{ 
    		if(num1>num2)
    		{ 
    			num1-=num2;
    		}
    		else
    		{ 
    			num2-=num1;
    		}
    	}
    	num1=num1*pow(2,count);
    	 printf("%d",num1);
    	 return 0;
    }