Mini-challenge: thư viện NumberUtils

Đây là mini-challenge khép lại Module 4. Không lý thuyết mới — bạn viết một class NumberUtils chứa các method tĩnh xử lý số nguyên thường dùng: GCD, LCM, kiểm tra nguyên tố, tính tổng varargs, giai thừa. Kết hợp đủ các khái niệm: khai báo method, overloading, varargs, recursion, scope — tất cả cùng một file.

Sau bài này bạn có 1 class NumberUtils tái sử dụng được, và hiểu quy trình thiết kế một bộ utility: tên method rõ, signature nhất quán, không leak state, có validation input.

🎯 Đề bài

Viết class NumberUtils với các method public static sau:

1. gcd(int a, int b) — Ước chung lớn nhất (Greatest Common Divisor). Return int.
2. gcd(int... nums) — Overload varargs cho nhiều số: gcd(12, 18, 24). Return int.
3. lcm(int a, int b) — Bội chung nhỏ nhất (Least Common Multiple). Dùng gcd.
4. isPrime(int n) — true nếu n là số nguyên tố; false cho số ≤ 1.
5. sum(int... nums) — Tổng tất cả argument. sum() trả 0.
6. factorial(int n) — Giai thừa (recursion). Ném IllegalArgumentException nếu n < 0.

Output mẫu:

gcd(12, 18) = 6
gcd(12, 18, 24) = 6
lcm(4, 6) = 12
isPrime(17) = true
isPrime(15) = false
sum() = 0
sum(1, 2, 3, 4, 5) = 15
factorial(5) = 120

🔍 Phân tích I-P-O

Input: Tham số tuỳ method. Varargs với 0+ số.

Processing: Dùng công thức toán / thuật toán:

• GCD: thuật toán Euclid — gcd(a, b) = gcd(b, a % b), base case b == 0 → a.
• LCM: lcm(a, b) = a * b / gcd(a, b). Chú ý overflow với số lớn.
• isPrime: trial division đến sqrt(n).
• Sum: vòng for cộng.
• Factorial: đệ quy n * factorial(n-1), base 0! = 1.

Output: Giá trị trả về kiểu tương ứng, hoặc exception khi input không hợp lệ.

📦 Concept dùng trong bài

▶️ Starter code

Copy file này, điền vào các TODO:

public class NumberUtils {

    // TODO: gcd(int a, int b) — thuat toan Euclid (recursion hoac iterative)

    // TODO: gcd(int... nums) — reduce qua day, dung gcd(int, int)
    //       Nem IllegalArgumentException neu so luong < 2

    // TODO: lcm(int a, int b) — a / gcd(a, b) * b de tranh overflow

    // TODO: isPrime(int n) — false neu n <= 1, true neu n == 2,
    //       false neu n chia het 2, loop i tu 3 den sqrt(n) buoc 2

    // TODO: sum(int... nums) — for-each cong

    // TODO: factorial(int n) — recursion, nem IllegalArgumentException neu n < 0

    public static void main(String[] args) {
        System.out.println("gcd(12, 18) = " + gcd(12, 18));
        System.out.println("gcd(12, 18, 24) = " + gcd(12, 18, 24));
        System.out.println("lcm(4, 6) = " + lcm(4, 6));
        System.out.println("isPrime(17) = " + isPrime(17));
        System.out.println("isPrime(15) = " + isPrime(15));
        System.out.println("sum() = " + sum());
        System.out.println("sum(1, 2, 3, 4, 5) = " + sum(1, 2, 3, 4, 5));
        System.out.println("factorial(5) = " + factorial(5));
    }
}

javac NumberUtils.java
java NumberUtils

Dành 20–25 phút tự làm trước khi xem gợi ý.

💡 Gợi ý

public static int gcd(int a, int b) {
    if (b == 0) return Math.abs(a);
    return gcd(b, a % b);
}

public static int gcd(int... nums) {
    if (nums.length < 2) throw new IllegalArgumentException("Need at least 2 numbers");
    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        result = gcd(result, nums[i]);
    }
    return result;
}

public static int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return Math.abs(a / gcd(a, b) * b);
}

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; (long) i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

public static long factorial(int n) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative, got " + n);
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

✅ Lời giải

public class NumberUtils {

    public static int gcd(int a, int b) {
        if (b == 0) return Math.abs(a);
        return gcd(b, a % b);
    }

    public static int gcd(int... nums) {
        if (nums.length < 2) {
            throw new IllegalArgumentException("Need at least 2 numbers, got " + nums.length);
        }
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            result = gcd(result, nums[i]);
        }
        return result;
    }

    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        return Math.abs(a / gcd(a, b) * b);
    }

    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; (long) i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static int sum(int... nums) {
        int total = 0;
        for (int n : nums) total += n;
        return total;
    }

    public static long factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative, got " + n);
        }
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("gcd(12, 18) = " + gcd(12, 18));
        System.out.println("gcd(12, 18, 24) = " + gcd(12, 18, 24));
        System.out.println("lcm(4, 6) = " + lcm(4, 6));
        System.out.println("isPrime(17) = " + isPrime(17));
        System.out.println("isPrime(15) = " + isPrime(15));
        System.out.println("sum() = " + sum());
        System.out.println("sum(1, 2, 3, 4, 5) = " + sum(1, 2, 3, 4, 5));
        System.out.println("factorial(5) = " + factorial(5));
    }
}

🎓 Mở rộng

Đã hoàn thành bài cơ bản? Thử tiếp:

Mức 1 — Viết unit test với JUnit 5:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class NumberUtilsTest {
    @Test void gcdBasic() { assertEquals(6, NumberUtils.gcd(12, 18)); }
    @Test void gcdVarargs() { assertEquals(6, NumberUtils.gcd(12, 18, 24)); }
    @Test void lcmZero() { assertEquals(0, NumberUtils.lcm(0, 5)); }
    @Test void isPrimeEdge() { assertFalse(NumberUtils.isPrime(1)); }
    @Test void factorialNegative() {
        assertThrows(IllegalArgumentException.class, () -> NumberUtils.factorial(-1));
    }
}

Mức 2 — Thêm BigInteger cho factorial lớn:

factorial(20) vẫn fit long, nhưng factorial(25) đã overflow. Thêm overload:

import java.math.BigInteger;

public static BigInteger factorialBig(int n) {
    if (n < 0) throw new IllegalArgumentException(...);
    BigInteger result = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
        result = result.multiply(BigInteger.valueOf(i));
    }
    return result;
}

Chú ý: đổi sang iterative vì recursion với BigInteger tạo nhiều intermediate object — iterative hiệu quả hơn.

Mức 3 — Memoize isPrime:

import java.util.BitSet;

private static final BitSet PRIME_CACHE = new BitSet(10_000);
private static final BitSet COMPUTED = new BitSet(10_000);

public static boolean isPrime(int n) {
    if (n < COMPUTED.size() && COMPUTED.get(n)) {
        return PRIME_CACHE.get(n);
    }
    boolean result = /* tinh nhu cu */;
    if (n < COMPUTED.size()) {
        COMPUTED.set(n);
        if (result) PRIME_CACHE.set(n);
    }
    return result;
}

Trade-off: tiết kiệm thời gian với queries lặp lại, tốn memory. Chỉ worth nếu benchmark cho thấy bottleneck.

Mức 4 — Sieve of Eratosthenes cho primesUpTo(int n):

Thay vì check từng số, xây bảng nguyên tố đến n bằng sàng:

public static int[] primesUpTo(int n) {
    boolean[] isComposite = new boolean[n + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            primes.add(i);
            for (int j = i + i; j <= n; j += i) isComposite[j] = true;
        }
    }
    return primes.stream().mapToInt(Integer::intValue).toArray();
}

O(n log log n) — nhanh hơn gọi isPrime cho từng số từ 2 đến n.

✨ Điều bạn vừa làm được

Hoàn thành mini-challenge này, bạn đã:

• Khai báo 6 method tĩnh với signature khác nhau, theo đúng Java convention (tên camelCase, động từ hoặc is<X>).
• Áp dụng overloading cho gcd(int, int) vs gcd(int...) — compiler tự chọn phiên bản theo số argument.
• Dùng varargs cho số lượng tham số tuỳ ý, kèm validation khi số argument không đủ.
• Viết recursion an toàn: base case rõ, recursive case tiệm cận base, depth có giới hạn.
• Xử lý overflow bằng kỹ thuật "chia trước, nhân sau" (lcm) và cast long (isPrime).
• Validate input với IllegalArgumentException — spec Java chuẩn cho "input không hợp lệ".
• Chọn đúng return type (int đủ cho gcd/lcm; long cho factorial; boolean cho isPrime).

Chúc mừng — bạn đã hoàn thành Module 4! Đây là lúc bạn có thể phân rã chương trình thành nhiều hàm nhỏ thay vì dồn vào main. Module 5 sẽ bước vào OOP: class, object, constructor, field, encapsulation — nơi method thôi làm việc một mình mà gắn vào đối tượng có trạng thái.