Lesson 02 (T5) — Số nguyên tố & Đồng dư
1. Sàng Eratosthenes
Kéo N — sàng gạch bỏ mọi bội số: xanh = nguyên tố, đỏ gạch = hợp số. Thử: N = 100 — đúng 25 số nguyên tố; kéo lên 200 xem mật độ thưa dần.
N = 100
Số nguyên tố ≤ N: 25
2. Phân tích thừa số nguyên tố
Nhập n — phân tích thừa số, đếm số ước và tính φ(n). Thử: 504 = 2³·3²·7 → số ước = (3+1)(2+1)(1+1) = 24.
3. Tính a^N mod m
Dùng định lý Fermat / Euler để tính nhanh khi N rất lớn.
4. 🌍 Đời sống thực tế — Mã vạch & thứ trong tuần
Số học đồng dư (modular arithmetic) chạy ngầm trong mọi mã vạch bạn quét và mọi câu hỏi "sau N ngày là thứ mấy".
1. Kiểm tra mã vạch EAN-13 / ISBN-13 (mod 10)
Mã 13 số:
2. Sau N ngày là thứ mấy? (mod 7)
Số ngày kể từ hôm nay (Thứ Hai):