Số nguyên tố là gì?
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước: số 1 và chính nó. Ví dụ 2, 3, 5, 7, 11, 13 đều là số nguyên tố. Số 2 là số nguyên tố chẵn duy nhất. Một số lớn hơn 1 mà có nhiều hơn hai ước (như 4 = 2×2, 6 = 2×3, 9 = 3×3) gọi là hợp số. Riêng số 1 không phải số nguyên tố cũng không phải hợp số.
Sàng Eratosthenes hoạt động thế nào?
Sàng Eratosthenes là một thuật toán cổ (khoảng 2200 năm trước) để liệt kê mọi số nguyên tố không vượt quá N. Ý tưởng rất đơn giản: viết các số từ 2 đến N, rồi lần lượt loại bỏ các bội của từng số nguyên tố. Những số sống sót chính là số nguyên tố.
- Viết tất cả các số từ 2 đến N.
- Lấy số nhỏ nhất chưa bị gạch (lần đầu là số 2) — đó là một số nguyên tố.
- Gạch bỏ mọi bội của số đó (4, 6, 8, … với số 2), vì chúng chia hết cho nó nên là hợp số.
- Lặp lại với số nhỏ nhất còn lại tiếp theo (3, rồi 5, rồi 7…) cho đến khi vượt quá √N.
- Mọi số chưa bị gạch còn lại đều là số nguyên tố.
Vì sao có thể dừng ở √N?
Giả sử một số hợp số m ≤ N. Khi đó m = p × q với p ≤ q. Vì p là số nhỏ hơn nên p ≤ √m ≤ √N. Nghĩa là mọi hợp số đều có một ước nguyên tố không vượt quá √N. Vậy khi ta đã gạch hết bội của mọi số nguyên tố ≤ √N thì mọi hợp số đều đã bị gạch — không cần đi xa hơn.
Ví dụ với N = 100 thì √100 = 10, nên chỉ cần xét các số nguyên tố 2, 3, 5, 7 (đều ≤ 10) là đủ để gạch hết hợp số. Đó là lý do sàng chạy rất nhanh. Một mẹo nhỏ: khi xét số nguyên tố p, có thể bắt đầu gạch ngay từ p² vì các bội nhỏ hơn (2p, 3p…) đã bị các số nguyên tố nhỏ hơn gạch rồi.
Sự thật thú vị về số nguyên tố
Có vô số số nguyên tố. Euclid đã chứng minh điều này từ hơn 2000 năm trước: dù bạn liệt kê bao nhiêu số nguyên tố, vẫn luôn còn số nguyên tố lớn hơn — danh sách không bao giờ kết thúc.
Số nguyên tố sinh đôi. Đó là cặp số nguyên tố cách nhau đúng 2 đơn vị, như (3, 5), (11, 13), (17, 19). Các nhà toán học vẫn chưa biết chắc liệu có vô số cặp như vậy hay không — đây là một bài toán mở nổi tiếng.
Câu hỏi thường gặp
Số 1 có phải số nguyên tố không? Không. Số 1 chỉ có một ước là chính nó, trong khi số nguyên tố phải có đúng hai ước. Vì vậy 1 không phải số nguyên tố, cũng không phải hợp số.
Số nguyên tố nhỏ nhất là số nào? Là số 2 — và đó cũng là số nguyên tố chẵn duy nhất, vì mọi số chẵn khác đều chia hết cho 2.
Ứng dụng thực tế
Số nguyên tố không chỉ là chuyện trên lớp — chúng có mặt khắp nơi:
- 🔐 Mật mã RSA: bảo mật ngân hàng, mua sắm online dựa trên việc nhân hai số nguyên tố rất lớn thì dễ, nhưng phân tích ngược lại thì cực khó.
- 🧮 Phân tích ra thừa số nguyên tố: mọi số tự nhiên đều viết được duy nhất thành tích các số nguyên tố.
- 🔢 Tìm ƯCLN và BCNN nhanh nhờ phân tích thừa số nguyên tố.
- 💻 Hàm băm và bảng băm trong tin học thường dùng kích thước là số nguyên tố để giảm va chạm.