最大公約數、最小公倍數

文章目錄

• 引入
• 最大公約數
• 最小公倍數百度百科
• 分析
• 輾轉相除法
• 更相減損術
• 窮舉法

引入

求兩個非負整數的最大公約數和最小公倍數？
           

最大公約數

最大公約數百度百科：

最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記号。求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。

最小公倍數百度百科

最小公倍數百度百科:

兩個或多個整數公有的倍數叫做它們的公倍數，其中除0以外最小的一個公倍數就叫做這幾個整數的最小公倍數。整數a，b的最小公倍數記為[a，b]，同樣的，a，b，c的最小公倍數記為[a，b，c]，多個整數的最小公倍數也有同樣的記号。

與最小公倍數相對應的概念是最大公約數，a，b的最大公約數記為（a，b）。關于最小公倍數與最大公約數，我們有這樣的定理：(a,b)x[a,b]=ab(a,b均為整數)。

分析

求最大公約數和最小公倍數是由方法的，如果說12、8的最大公約數我們一看就知道是4，12、8的最小公倍數一看就是24。寫程式不是一看就能寫出來，我們需要從中找出算法，将算法寫在程式中，常見的算法由輾轉相除法、更相減損發、質因數分解法、短除法

• 輾轉相除法、更相減損術求的是最大公約數，最小公倍數：a*b/最大公約數

輾轉相除法

每種算法的核心不一樣，拿輾轉相除法，怎麼求最大公約數、最小公倍數：

最大公約數
           

• 比較出兩數的大小
• 大數%小數求餘，小數指派給之前的大數，餘數指派給小數
• 當餘數等于0結束

  最小公倍數
             

• 兩數相乘/最大公約數

我們要做的是把算法的邏輯寫入程式

c

# include <stdio.h>

//聲明最大公約數函數
//int test1(a,b);
//聲明最小公倍數函數
//int test2(a,b); 

int main()
{
	//首先需要兩數
	int a,b;
	//輸入兩數 
	scanf("%d%d",&a,&b);
	
	//調用求最小公倍數函數 ,将a、b兩個值傳遞過去 
	test2(a,b);
	
   return 0;

}

//最大公約數是int，把函數傳回值類型設定為int 
int test1(a,b) {
	/**
	兩數的最大公約數和最小公倍數
	最大公約數舉個例子(12、8 的最大公約數是4) 
	最小公倍數舉個例子(12、8 的最小公倍數是24) 
	*/ 
	
	//網上有很多算法求最大公約數和最小公倍數 ，每種算法的核心不一樣 
	/**
	輾轉相除法
	1.比較出兩數的最大值
	2. 大數%小數求餘，小數指派給之前的大數，餘數指派給小數
	3.當餘數位0結束 
	*/ 
	
	//自定義a必須大于b,定義一個中間變量
	int t; 
	if(a<b){
		t = a;
		a = b;
		b = t;
	} 
	
	//循環求餘數，當小數b也就是餘數等于0，就結束循環
	while(b!=0){
		t=a%b;
		a = b;
		b = t;
	}
	
	printf("最大公約數:%d\n",a);
	
	return a;
} 

//最小公倍數是一個int類型，把返函數回值類型設定為int 
int test2(int a, int b) {
	
	//定義變量接收最大公約數
	int t = test1(a,b); 
	
	//列印最小公倍數
	printf("最小公倍數:%d\n",a*b/t); 
	
	//根據兩數相乘除以最大公約數,獲得最小公倍數 
	return a*b/t;
} 
           

為了友善記憶，通過餘數，找到最大公約數
           

更相減損術

更相減損術百度百科

更相減損術是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計的，但它适用于任何需要求最大公約數的場合。

九章算法百度百科

《九章算法比類大全》是明代吳敬撰寫的算書，亦名《九章詳注比類算法大全》。明代前期的算書，十卷首一卷，成書于1450年。

了解：

沒想到明代都有算法一說，中國在明代還是比較繁榮的。更相減損術是出自《九章算術》的一種求最大公約數的算法

• 判斷傳入的兩數是否都是偶數例如a、b
  • 如果

    a%b==0

    ,最大公約數是b

  • a/=2、 b/=2 當while(a%2==0 && b%2==0)

    錯誤結束條件 使用2約減，使用循環判斷約減了幾次，最大公約數是 約減次數*2
• 如果傳入的兩數不為偶數，使用簡損法，自定義a必須大于b，定義轉換變量

  t，t=a-b、a=b>t?b:t、b=b<t?b:t，結束條件是(t == (a-b))

  ，傳回最大公約數是b的值

c

# include <stdio.h>


//聲明最小公倍數
int test2(a,b); 
//聲明最大公約數函數
int test3(a,b);

int main()
{
	//首先需要兩數
	int a,b;
	//輸入兩數 
	scanf("%d%d",&a,&b);
	printf("最大公約數：");
	printf("%d\n",test3(a,b));
	//調用更相減損法求最小公倍數 
	printf("最小公倍數：") ;
	printf("%d",test2(a,b));

   return 0;

}
//更相減損法求最大公約數函數 
int test3(int a,int b) {
	
	/**
	  1、判斷傳入的兩數是否都是偶數例如a、b
	  		如果a%b==0,最大公約數是b
	  		a/=2、 b/=2 當while(a%2==0 && b%2==0)`錯誤結束條件   使用2約減，使用循環判斷約減了幾次，最大公約數是 約減次數*2
	  2、如果傳入的兩數不為偶數，使用簡損法，自定義a必須b，定義轉換變量t，t=a-b、a=b>t?b:t、b=b<t?b:t，結束條件是(t == (a-b))
	*/
	
	int i = 0,t;
	
	//a%b==0,最大公約數是b
	if(a%b==0){
		return b;
	}
	//a/=2、 b/=2 當while(a%2==0 && b%2==0)`錯誤結束條件   使用2約減，使用循環判斷約減了幾次，最大公約數是 約減次數*2
	else if(a%2==0 && b%2==0){
		while(a%2==0 && b%2==0){
			a/=2;
			b/=2;
			i++;
		}
		return i*2;
	}
	//如果傳入的兩數不為偶數，使用簡損法，自定義a必須b，定義轉換變量t，t=a-b、a=b>t?b:t、b=b<t?b:t，結束條件是(t == (a-b)),傳回最大公約數是b的值
	else{
		//自定義a必須大于b
		if(a<b){
			t = a;
			a = b;
			b = t;
		} 
		while(1){
			t=a-b;
			a=b>t?b:t;
			b=b<t?b:t;
			if(b==(a-b)){
				break;
			}
		}
		//傳回最大公約數是b的值
		return b;
	} 
}


//最小公倍數是一個int類型，把返函數回值類型設定為int 
int test2(int a, int b) {
	
	//定義變量接收最大公約數
	int t = test3(a,b); 
	
	//根據兩數相乘除以最大公約數,獲得最小公倍數 
	return a*b/t;
} 
           

為了友善記憶，更相減損法，記住一點，它是通過內插補點找最大公約數
           

窮舉法

百度百科

窮舉法就是枚舉法，在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結論，那麼這結論是可靠的，這種歸納方法叫做枚舉法．

了解：

窮舉法有點像，我們直接從兩數中看出最大公約數和最小公倍數。而計算機這是通過循環去一個個比對出來。

• 從兩數中最小的數開始找，直到找到符合條件的數，

  a%t==0 && b%t==0

  遞減(最大公約數)
• 從最大值的倍數開始找，找到符合條件的值

  t%b==0

  遞增(最小公倍數)

  這裡的t是開始找的初始值，a、b是兩個數
             

# include <stdio.h>


//聲明最小公倍數
int test4(a,b); 
//聲明最大公約數函數
int test5(a,b);

int main()
{
	//首先需要兩數
	int a,b;
	//輸入兩數 
	//窮舉法求最大公約數，最小公倍數 
	scanf("%d%d",&a,&b);
	printf("最大公約數：");
	printf("%d\n",test4(a,b));
	printf("最小公倍數：") ;
	printf("%d",test5(a,b));

   return 0;

}

//定義最大公約數函數 
int test4(int a, int b) {
	//定義轉換變量
	int t;
	//找出最小值 
	t = (a>b)?b:a; 
	while(1){
		if(a%t==0 && b%t==0) {
			break;
		}
		//從兩數中最小的數開始找，直到找到符合條件的數，遞減 
		t--;
	} 
	//傳回最大公約數 
	return t; 
}

//定義最小公倍數函數 
int test5(int a,int b){
	//定義變量作為中間轉換變量 
	int t;
	//自定義a>b
	a=a>b?a:b;
	b=a<b?a:b;
	//把最大值賦給轉換變量
	t = a;
	//當找出一個符合最小公倍數的值結束循環 
	while(1) {
		if(t%b==0){
			break; 
		}
		//從兩數中最大數的倍數開始找，直到找到符合條件的數，遞增 
		t+=a;
	}
	//傳回最小公倍數 
	return t;
}
           

友善記憶：
最大公約數，通過兩數中的小的數，遞減找出最大公約數
最小公倍數，通過最大數的倍數遞增，找出最小公倍數