?前言

經過前期的數據結構和算法學習，開始以OD機考題作為練習題，繼續加強下熟練程度。

描述

正整數A和正整數B?的最小公倍數是指?能被A和B整除的最小的正整數值，設計一個算法，求輸入A和B的最小公倍數。

數據范圍：1≤𝑎,𝑏≤100000?1≤a,b≤100000?

輸入描述：

輸入兩個正整數A和B。

輸出描述：

輸出A和B的最小公倍數。

示例1

輸入：

5 7

輸出：

35

實現原理與步驟

最大公約數 (GCD) 的計算：

• 使用歐幾里得算法計算兩個數的最大公約數。
• 在 gcd 方法中，使用 while 循環不斷交換 a 和 b，并將 b 賦值為 a % b，直到 b 為0。最后返回 a 作為最大公約數。

最大公倍數 (LCM) 的計算：

• 使用公式?LCM(a,b)=∣a×b∣?/GCD(a,b)計算兩個數的最大公倍數。
• 在 lcm 方法中，先調用 gcd 方法計算兩個數的最大公約數，然后用上述公式計算最大公倍數。

實現代碼

import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區別int a = in.nextInt();int b = in.nextInt();if (a > b) {int temp = a;a = b;b = temp;}int res=lcm(a,b);System.out.println(res);}//最大公約數public static int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;}//最小公倍數public static int lcm(int a,int b){return a*b/gcd(a,b);}
}

1.QA: