Thuật toán để thách thức DeepSeek
**Sàng Eratosthenes** là một thuật toán cổ điển (**khoảng thế kỷ III TCN**) dùng để **tìm tất cả số nguyên tố nhỏ hơn một số cho trước**. Nó được đặt theo tên nhà toán học Hy Lạp **Eratosthenes**, người đã phát minh ra phương pháp này. Cơ chế hoạt động của nó giống như một "cái sàng" lọc dần các hợp số, chỉ giữ lại số nguyên tố.
### **Cách hoạt động**:
1. **Bước 1**: Liệt kê tất cả số tự nhiên từ **2 đến N** (giới hạn cần tìm số nguyên tố).
2. **Bước 2**: Bắt đầu từ số nhỏ nhất (**2**), loại bỏ tất cả **bội số của 2** (trừ chính số 2).
3. **Bước 3**: Chuyển sang số chưa bị loại tiếp theo (**3**), loại bỏ các bội số của 3.
4. **Bước 4**: Lặp lại quá trình này cho đến khi **số đang xét ≤ √N**.
5. **Bước 5**: Những số còn lại không bị loại là **số nguyên tố**.
### **Ví dụ minh họa** (Tìm số nguyên tố ≤ 30):
- **Bước 1**: Liệt kê số từ 2 đến 30.
- **Bước 2**: Loại bội của 2 (4, 6, 8, ..., 30), còn lại: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.
- **Bước 3**: Loại bội của 3 (9, 15, 21, 27), còn lại: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29.
- **Bước 4**: Loại bội của 5 (25), còn lại: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
- **Dừng lại** vì số tiếp theo (7) đã lớn hơn **√30 ≈ 5.47**.
→ **Kết quả**: Các số nguyên tố ≤ 30 là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
### **Ưu điểm**:
- **Hiệu quả** với số nhỏ hoặc trung bình (độ phức tạp: \(O(N \log \log N)\)).
- **Dễ hiểu và dễ cài đặt** bằng code hoặc thực hiện thủ công.
### **Nhược điểm**:
- **Tốn bộ nhớ** khi N rất lớn (ví dụ: N = 1 tỷ).
- **Không phù hợp** để kiểm tra tính nguyên tố của một số riêng lẻ.
---
### **Ứng dụng**:
- Tạo danh sách số nguyên tố phục vụ cho mã hóa (RSA), giải các bài toán toán học (như Giả thuyết Goldbach).
- Dùng trong giảng dạy để minh họa thuật toán đơn giản nhưng thông minh.
---
**Fun fact**: Sàng Eratosthenes vẫn được dùng trong các thư viện toán học hiện đại (như Python's `sympy`) để tạo số nguyên tố nhanh chóng!