Thuật toán Sàng nguyên tố

Sàng nguyên tố - Prime Number Sieve

Sàng nguyên tố là thuật toán do Eratosthenes đưa ra để tìm các số nguyên tố. Nó có đặc điểm khác với thuật toán khác là kiểm tra các số nguyên tố theo kiểu sàng lọc, xét tất cả những số cần kiểm, những số nào không phải là số nguyên tố thì bỏ đi. Thuật toán thích hợp cho bài toán tìm tất cả các số nguyên tố trong khoảng [a, b] mà đặc biệt hiệu quả khi khoảng cách giữa a, b là rất lớn.
Để tìm các số không phải số nguyên tố chỉ cần dựa vào các số nguyên tố ban đầu, VD số 2 là số nguyên tố thì các số chia hết cho 2 chắc chắn không phải là số nguyên tố, số 3 là số nguyên tố thì tất cả các số là bội của 3 đều bị loại bỏ, cứ như vậy những số được giữ lại là các số nguyên tố.