Tìm ước số chung lớn nhất của n số nguyên trong java

74
Lập trình Java

Để tìm ước số chung lớn nhất (USCLN) của nhiều số nguyên, ta có thể sử dụng thuật toán Euclid như sau:

  1. Tìm USCLN của 2 số đầu tiên bằng thuật toán Euclid (gọi là result).
  2. Tìm USCLN của result và số tiếp theo trong dãy và cập nhật result.
  3. Lặp lại bước 2 với các số tiếp theo trong dãy cho đến khi hết các số.

Dưới đây là mã nguồn Java cho bài toán trên:

public class USCLN {
    public static void main(String[] args) {
        int[] numbers = {12, 24, 36, 48, 60};
        int result = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            result = findUSCLN(result, numbers[i]);
        }
        System.out.println("USCLN: " + result);
    }

    public static int findUSCLN(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Trong đó, mảng numbers chứa các số nguyên cần tìm USCLN, và hàm findUSCLN thực hiện tìm USCLN của 2 số nguyên. Hàm main sử dụng vòng lặp để tìm USCLN của từng cặp số trong mảng numbers, sau đó in kết quả ra màn hình.