用Java解決最大公約數與最小公倍數問題

目錄

1.最大公約數

2.最小公倍數

1.最大公約數

題目：求兩個正整數的最大公約數。

解題思路：最大公約數我們可以利用循環的算法來計算。意思就是說,比如有兩個數字a,b（a>b）,它們的最大公約數肯定不會大于其中最小的那一個,即不會大于b。是以我們可以利用循環算法不斷地對數字a,b從1-b進行整除,看結果是否同時為0，直到找到那個最大的數字可以結果同時為0的情況。

方法一：

注意事項：   

    a.循環算法是從1~b進行整除的，不能将此變量設定為從0開始，否則運作時會報錯（by zero）;

    b.其實在程式設計時我們不需要一次性将所需變量全部設定出來，可以根據思路一邊寫一遍設定，防止思維混亂。

是以我們可得到如下代碼：

import java.util.Scanner;

public class TestDome {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        Scanner scanner1 = new Scanner(System.in);
        int b = scanner1.nextInt();

        int c = 0;
        int i = 1;
        int result=0;
        if(a>b){
            c=b;
        }else{
            c=a;
        }

        while(i<=c){
            if(a % i ==0 && b % i ==0){
                result = i;
            }
            i++;
        }
        System.out.println("最大公約數為" + result);
        }
 
    }

           

運作結果如下：

方法二： 

解題思路：輾轉相除法。舉例：12 和18        18 和 6

                  步驟一：先判斷a除以b是否為0，要是為0，結果直接輸出為b(也就是a,b兩個中最小的數字)。

                  步驟二：如果不是0，則用除數作為新的被除數，餘數作為新的除數，直到相除結果為0為止。（是以這裡需要用到循環）

                               也就是将b賦給a,将餘數c賦給b,直到相除結果為0為止,結果直接輸出為b。

 是以我們可得到如下代碼：

import java.util.Scanner;

public class TestDome {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        Scanner scanner1 = new Scanner(System.in);
        int b = scanner1.nextInt();

        int c =0;
        while(a % b != 0){
            c =a%b;
            a =b;
            b =c;
        }
        System.out.println("最大公約數："+ b);


    }
}
           

運作結果如下：

2.最小公倍數

題目：求兩個正整數的最小公倍數。

解題思路：最小公倍數 = 兩數的乘積 / 最大公約數。

是以我們可得到如下代碼：

import java.util.Scanner;

public class TestDome {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        Scanner scanner1 = new Scanner(System.in);
        int b = scanner1.nextInt();

        int c = 0;
        int i = 1;
        int result=0;
        if(a>b){
            c=b;
        }else{
            c=a;
        }

        while(i<=c){
            if(a % i ==0 && b % i ==0){
                result = i;
            }
            i++;
        }
        int result1=a* b/ result;
        System.out.println("最小公倍數為" + result1);
        }
 
    }
           

運作結果如下：