最大公约数

1.辗转相除法：

//获取最大公约数 
int getGCD(int a,int b){
    int temp;
    if(a < b){
      temp = a;
      a = b;
      b = temp;
    } 
    if(a%b == 0){
        return b; 
    }else{ 
        return getGCD(b,a%b); 
    } 

两个数的最大公约数是指能同时整除它们的最大正整数。 [1] 

设两数为a、b(a≥b)，求a和b最大公约数

  

的步骤如下：

(1)用a除以b(a≥b)，得

  

。

(2)若

  

，则

  

；

(3)若

  

，则再用b除以

  

，得

  

.

(4)若

  

，则

  

；若

  

，则继续用

  

除以

  

，......，如此下去，直到能整除为止。

其最后一个余数为0的除数即为

  

的最大公约数。

 

 

//减法求最大公约数
#include<stdio.h>
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    while(a!=b)
    {
        if(a>b)
        a-=b;
        else
        b-=a;
    }
    printf("%d",a);
}