計算最大公約數和最小公倍數是簡單常見的算法，他有多種方式實現，比如：窮舉法、輾轉相除法、相減法等等，方法很多，目的相同，下面就用其中一種方法，輾轉相除法來完成這個算法，下面將用計算機編程的方式實現。
9和15最大公約數為3 最大公約數和最小公倍數的概念
最大公約數指某幾個整數共有約數中最大的一個。最小公倍數是某幾個整數公有的倍數中最小的一個正整數。 它們之間的關系最大公約數=兩數之積/最小公倍數，所以只要求出一個另外一個自然通過簡單的計算求出來了。
輾轉相除法，算法舉例有兩整數a和b： ① a%b得余數c ② 若c=0，則b即為兩數的最大公約數 ③ 若c≠0，則a=b，b=c，再回去執行① 例如求35和15的最大公約數過程為： 35÷15 余5，,15÷5余0，5即為最大公約數
代碼實現
圖片代碼 演示結果
結果 文本代碼
import java.util.Scanner; public class S { public static void main(String args[]){ Scanner s=new Scanner(System.in); int a=s.nextInt(); int b=s.nextInt(); int m=a;//用m記錄a int n=b;//用n記錄b int c=1;//定義余數 while(c!=0){//只要余數不等于0，就做循環 c=a%b; a=b; b=c; System.out.println(a+b+c); } System.out.println('最大公約數'+a);//此時的a是原來的b System.out.println('最小公倍數數'+m*n/a);//利用關系計算出最小公倍數 } }
結語
至此這個算法就演示完畢了，當然實現的方法好多，效率也不一樣，這里只演示了一種算法，有興趣的可以試試其他方法。 每天持續分享計算機編程知識，c語言，java，php等等，歡迎交流，一起進步，歡迎收藏，轉發，關注趣IT科技，喜歡就請點個贊吧。
|
