Giải thuật sàng nguyên tố Eratosthenes

Lịch sử

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) “phát minh” ra.

Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes

Thuật toán

• Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,…, n).
• Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
• Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
• Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p và nhỏ hơn hoặc bằng căn bậc 2 của n . Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

Hình ảnh minh họa cho Giải thuật

Giả mã tường minh:

Input: một số nguyên n > 1
Cho A là một mảng boolean, được đánh số từ 2 đến n,
khởi tạo bằng cách gán tất cả phần tử trong mảng là true.
for i = 2, 3, 4,..., √n:
if A[i] is true:
for j = i2, i2+i, i2+2i,..., n:
A[j]:= false // Loại bỏ các bội.

Lập trình

Trong thực tế thì chúng ta có thể thực hiện giải thuật nhanh hơn nữa qua việc thực hiện ví dụ dưới đây:

Ví dụ. Nhập số nguyên dương n. Liệt kê các số nguyên tố từ 1 đến n

Code C++:

Ở đây, các bạn cần đặc biệt lưu ý với mảng ngTo[nmax]. Các chỉ số chạy trong mảng f[i] chính là các giá trị của dãy số cần xét xem có phải là số nguyên tố hay không? Còn giá trị của các phần tử trong mảng f[i] chỉ là hai giá trị 0 và 1. Trong đó, nếu f[i] = 0 thì i không phải là số nguyên tố, ngược lại nếu f[i] = 1 thì i là số nguyên tố. Hiểu rõ vấn đề các bạn có thể thực hiện bài tập theo chương trình dưới đây:

#include<iostream>
#include<cmath>

using namespace std;

#define nmax 100001
int n;
int ngTo[nmax];

void sangNT() {
    for(int i = 0;i <= n; i++)
        ngTo[i] = 1; // Gán tất cả các giá trị i là số nguyên tố.
    ngTo[0] = ngTo[1] = 0; // Loại bỏ số 0 và số 1
    for (int i = 2; i <= sqrt(n); i++) // Duyệt các phần từ từ 2 đến sqrt(n)
        if (ngTo[i]) // Nếu i là số nguyên tố thì bắt đầu tìm kiếm các bội của i
            for (int j = i*i; j <= n; j += i) // Bắt đầu từ i^2 đến n.
                ngTo[j] = 0; // Loai bo tat ca cac boi cua i
}

int main() {
    cin >> n;
    sangNT();
    for(int i = 0; i <= n; i++)
        if(ngTo[i])
            cout << i << " ";
    return 0;
}