計算器如何求最大公約數-tft每日頭條

1 求最大公約數的經典方法

我們上學的時候都求過最大公約數，大概是小學 5 年級問題，但是我們好像沒有在哪個計算器上直接找到求最大公約數的按鍵，有時候兩個數字很大，求起來還是挺麻煩的，但如果借助電腦這件事就容易了，今天我們一起在電腦上用小學一年級同學也會使用的Scratch軟件編程幫我們實現自動求最大公約數的功能。

先回顧一下求最大公約數的數學邏輯。求最大公約數是數學中的一個經典問題，數學家們想出來很多種方法，其中最早的一種方法叫輾轉相除法，出現在距今 2300 多年前的古希臘數學家歐幾裡得所著的《幾何原本》一書中，所以也被稱為歐幾裡得算法，它是目前仍然在使用的算法之一。下面我們就一起來看一下這個算法。

計算器如何求最大公約數（如何自動化求最大公約數）1

題目：A、B有最大公約數K，并且A > B，已知A, B來求K。

用輾轉相除法求K的過程：

2 推導過程

舉兩個例子：

1. 12和9兩個數求最大公約數。

2. 5767和4453兩個數求最大公約數。

說白了輾轉相除法求最大公約數就是：不斷求兩數相除的餘數，用除數代替被除數，餘數代替除數，直到餘數為0，此刻的除數就是最大公約數。

3 編程實現

知道輾轉相除法的原理，程序就很容易編出來了（如下圖），比單純學數學好的地方是，不管多大的數，會編程序的同學随時都可以求着玩，分分鐘出答案。

計算器如何求最大公約數（如何自動化求最大公約數）2

計算器如何求最大公約數（如何自動化求最大公約數）3

其實用輾轉相除法不但可以求最大公約數，隻要稍微變化一下，還可以将10進制轉化成2進制。後面我們會繼續寫文章來看看這個神奇的輾轉相除法如何對進制進行轉化。