Lesson 46 — Thuật toán số học
Ba mô-đun tương tác: sàng Eratosthenes, thuật toán Euclid (GCD), và fast exponentiation. Bấm "Chạy từng bước" để xem từng thao tác.
1. Sàng Eratosthenes
Lưới 1..n. Chọn nguyên tố nhỏ nhất chưa gạch, rồi gạch mọi bội của nó (từ p²). Độ phức tạp O(n log log n).
Nhập n rồi bấm "Chạy từng bước".
chưa xét
nguyên tố
hợp số (đã gạch)
đang gạch
2. Euclid GCD — gcd(a, b) = gcd(b, a mod b)
Liên tục thay (a, b) ← (b, a mod b) tới khi b = 0; khi đó a là GCD. O(log min(a,b)).
Nhập a, b rồi bấm "Chạy từng bước".
| Bước | a | b | a mod b |
|---|
3. Fast exponentiation — aⁿ mod m
Duyệt bit của n: bit 1 → nhân base vào result; luôn bình phương base; bỏ bit thấp. Chỉ ⌈log₂n⌉ vòng.
Nhập a, n, m rồi bấm "Chạy từng bước".
n = – (nhị phân)
| Vòng | n hiện tại | bit thấp | base | result |
|---|