最大公约数的性质以及求解方法

 最大公约数是指两个不同时为0的正数a和b的公约数中的最大值。记做

。下面是公约数的一些性质：

1. 

2. 

3. 

4. 

5. 

      对于任意

   

6. 

    是a与b的线性集合

   

   中的最小元素

最大公约数的求解方法，最先想打的是下面的解法：

int gcd(int a, int b){
	int ans = 1;
	for(int i = 1; i <= min(a, b); i++){
		if(a % i == 0 && b % i == 0){
			ans = max(ans, i);
		}
	}
	return ans;
}
           

 我们可以把上面的程序变化一下，可以得到下面的程序。 

int gcd(int a, int b){
	for(int i = min(a, b); i >= 1; i--){
		if(a % i == 0 && b % i == 0){
			return i;
		}
	}
}
           

下面我们提出另外的一种解法（辗转相除法）：

int gcd(int a, int b){
	a = max(a, b);
	b = min(a, b);
	while(a % b != 0){
		int tem = a % b;
		a = b;
        b = tem;
	}
	return b;
}
           

这种方法还可以写成递归的形式：

int gcd(int a, int b){
    if(b==0)
        return a;
    else
        return gcd(b, a%b);
}
           

还有一种方法是辗转相减法：

int gcd(int a, int b){
	while(1){
		if(a > b){
			a -= b;
		}
		else if(a < b){
			b -= a;
		}
		else{
			return a;
		}
	}
}
           

写成递归的形式：

int gcd(int a, int b){
	if(a > b){
		return gcd(a - b, b);
	}
	else if(a < b){
		return gcd(a, b - a);
	}
	else{
		return a;
	}
}