Sàng số nguyên tố
Kiểm tra từng số xem có phải số nguyên tố hay không rất chậm. Sàng Eratosthenes giải quyết việc đó bằng cách loại bỏ hàng loạt hợp số cùng lúc. Đây là nền tảng cho các thuật toán tìm số nguyên tố mà máy tính vẫn dùng ngày nay.
Phương pháp "sàng" này do nhà toán học Hy Lạp Eratosthenes nghĩ ra khoảng 200 năm TCN (xem thêm bối cảnh số nguyên tố ở module "Số nguyên tố & hình chữ nhật" ngay trước bài này).
Ô được viền cam là ô đến lượt, hãy bấm đúng ô đó. Bấm xong, mọi bội số của nó tự động bị gạch, rồi ô nhỏ nhất còn sống sót tiếp theo sẽ đến lượt. Số 1 không phải là số nguyên tố.
Nguyên lý: một số là hợp số nếu nó là bội của một số nhỏ hơn nó.
Bài học: gạch bỏ theo thứ tự từ nhỏ đến lớn thì số nào còn lại là số nguyên tố. Không cần đoán, không cần bấm hết mọi số, chỉ cần sàng đến khoảng √1000 ≈ 31.