輾轉相除法

什么是輾轉相除法？

輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德算法。

輾轉相除法是如何求倆個自然數的最大公約數的？

話不多說上例題：

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

簡單來說，現在有a,b倆個數，先拿a除以b得到余數c，如果c不等于0的話，就把除數b的值賦給a,把余數c的值賦給b，再拿新的a除以新的b，得到新的c以此類推……如果得到的余數c等于0的話，那么之前的除數b就是最大公約數。

求倆個數的最大公約數

public static void main(String[] args) {int a = 319;int b = 377;int c = a % b;while(c != 0){a = b;b = c;c = a % b;}System.out.println("最大公約數 "+b);}

?求倆個數的最小公倍數

最小公倍數=兩數的乘積/最大公約（因）數

代碼和上題類似

public static void main(String[] args) {int a = 9;int b = 3;int a1 = a;//保留aint b1 = b;//保留bint c = a1 % b1;while(c != 0){a1 = b1;b1 = c;c = a1 % b1;}System.out.println("最小公倍數數 "+(a*b)/b1);}

總結

以上是生活随笔為你收集整理的轻松掌握辗转相除法（原理＋俩道简单编程题详解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。