Tìm bội số chung nhỏ nhất (BSCNN) của n số nguyên trong Java

Bội số chung nhỏ nhất của 2 số nguyên

Bội số chung nhỏ nhất (BSCNN) của hai số nguyên là số nguyên dương nhỏ nhất chia hết cho cả hai số đó. Để tìm BSCNN của hai số nguyên a và b, ta cần tìm ước số chung lớn nhất (USCLN) của a và b, sau đó áp dụng công thức:

BSCNN(a,b) = (a*b)/USCLN(a,b)

Với n số nguyên, ta cần thực hiện các bước sau:

• Tìm BSCNN của hai số đầu tiên.
• Tiếp tục tìm BSCNN của kết quả trên và số tiếp theo cho đến khi hết các số.

Các từ khóa cho bài toán này có thể gồm: BSCNN, số nguyên, USCLN, chia hết, công thức, vòng lặp.

Dưới đây là ví dụ về cách tìm bội số chung nhỏ nhất của hai số nguyên trong Java:

public class BSCNN {
   public static int timUSCLN(int a, int b) {
      if (b == 0) {
         return a;
      }
      return timUSCLN(b, a % b);
   }

   public static int timBSCNN(int a, int b) {
      return (a * b) / timUSCLN(a, b);
   }

   public static void main(String[] args) {
      int a = 12;
      int b = 30;
      System.out.printf("BSCNN cua %d va %d la: %d", a, b, timBSCNN(a, b));
   }
}

Chương trình trên sử dụng hai phương thức timUSCLN và timBSCNN để tính ước số chung lớn nhất và bội số chung nhỏ nhất của hai số nguyên. Trong phương thức timUSCLN, chúng ta sử dụng đệ quy để tìm ra ước số chung lớn nhất của hai số. Trong phương thức timBSCNN, chúng ta tính bội số chung nhỏ nhất của hai số bằng cách nhân hai số đó và chia cho ước số chung lớn nhất của chúng.

Trong ví dụ trên, chúng ta tìm bội số chung nhỏ nhất của hai số nguyên là 12 và 30, kết quả thu được là 60.

Bội số chung nhỏ nhất của n số nguyên

Để tìm BSCNN của n số trong Java, ta có thể sử dụng thuật toán sau:

1. Khởi tạo biến result bằng giá trị của số đầu tiên trong dãy số.
2. Duyệt từng số trong dãy, tại mỗi số thực hiện các bước sau:
   • Tìm ước số chung lớn nhất (USCLN) của result và số hiện tại.
   • Nhân result với số hiện tại, chia cho USCLN tìm được ở bước trên.
3. Trả về giá trị result là BSCNN của dãy số.

Dưới đây là ví dụ minh họa cho thuật toán trên:

public class BSCNN {
    // Hàm tính USCLN của hai số
    public static int USCLN(int a, int b) {
        if (b == 0) {
            return a;
        }
        return USCLN(b, a % b);
    }
 
    // Hàm tính BSCNN của n số
    public static int BSCNN(int arr[], int n) {
        int result = arr[0];
        for (int i = 1; i < n; i++) {
            result = (result * arr[i]) / USCLN(result, arr[i]);
        }
        return result;
    }
 
    public static void main(String[] args) {
        int arr[] = {4, 6, 12, 16, 20};
        int n = arr.length;
        System.out.println("BSCNN của dãy số là: " + BSCNN(arr, n));
    }
}

Trong ví dụ này, ta có một dãy số arr gồm 5 số nguyên. Chương trình sử dụng hàm BSCNN để tính BSCNN của dãy số và in ra kết quả là 240.