編程之美2.7 最大公約數，最小公倍數

      書中的題目是求兩個數的最大公約數，其實這個問題時當我們學習C語言的時候老師就講過的算法，和教學中的求素數是一個類型的問題。

      我們當時學的方法是 “輾轉相除法”，即利用公式： f(x, y) = f(y, x % y)，直到 x % y == 0，取x就是兩個數的最大公約數。

      但是書中說道，乘除運算太浪費時間了，所以，我們可以換一種方法去思考這個問題，乘除不能用，就只能是加減了，所以，書中利用如果一個數能夠同時整除x和y，則必能同時整除x-y和y，所以我們定義x和y的最大公約數是f(x,y),那么依據上面的思想，可以得到f(x,y) = f(x-y,y)。

      函數聲明如下：

      源代碼如下：

      既然說到了最大公約數，那么和它相對應的是最小公倍數，不記得是上幾年級的時候，我們就學過一個公式，兩個數的最小公倍數計算方法是 : (x * y) / 最大公約數(x, y)。

      函數聲明如下：

      源代碼如下：

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈