最大公約數的性質以及求解方法

 最大公約數是指兩個不同時為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;
	}
}