求最大公約數以及最小公倍數

最大公約數(greatest common divisor因子, GCD)。

最小公倍數(least common multiple倍數, LCM)。

1.群舉法

首先給出兩個數a和b，從兩數較小的數開始，找到滿足a和b同時可以被其整除的最大的約數。

#include <stdio.h>
int gcd(int a, int a)
{
	int temp = 0;
	temp = (a<b) ? a : b;
	while (temp > 0)
	{
		if ((a%temp == 0) && (b%temp == 0))
			break;
		--temp;
	}
	return temp;
}
           

2.輾轉相除法

首先簡單介紹一下輾轉相除法： 輾轉相除法又名歐幾裡得算法，是求最大公約數的一種方法。它的具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反複，直到最後餘數是0為止。最後的餘數為0時的除數就是這兩個數的最大公約數。

非遞歸版本：

#include <stdio.h>
//不用判斷兩個數的大小關系，因為小數除大數
//第一次除完就轉換為大數除小數了
int gcd(int a, int b)
{
	while (b > 0)
	{
		int rem = a % b;
		a = b;
		b = rem;
	}
	return a;
}
           

遞歸版本：

int gcd(int a, int b) //求兩個數的最大公約數
{
	if ((a%b) == 0)
		return b;
	else
		return GCD(b, a%b);
}
           

3.更相減損法

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

測試代碼：

#include <stdio.h>
int main()
{
	int a = 9, b = 21;
	int temp = gcd(a, b);
	printf("%d\n", temp);
	return 0;
}
           

求最小公倍數：

因為兩個數的最大公約數和最小公倍數有如下關系：

最大公約數 x 最小公倍數 = 兩數的乘積
           

是以可以用最大公約數直接求最小公倍數。

int lcm(int a, int b)  //求兩個數的最小公倍數
{
	return a*b/gcd(a, b);
}
           

窮舉法求兩數的最小公倍數：

#include <stdio.h>
int lcm(int a, int b)
{
	int temp = 0;
	if (a < b)
	{
		a = a + b;
		b = a - b;
		a = a - b;
	}
	temp = a;
	while (temp % b != 0)
		temp += a;
	return  temp;
}
int main()
{
	int a = 3, b = 5;
	int temp = lcm(a, b);
	printf("%d\n", temp);
	return 0;
}