✨Sàng Eratosthenes

[[Eratosthenes]] Sàng Eratosthenes là một thuật toán cổ xưa để tìm các số nguyên tố trong một đoạn các số tự nhiên. Thuật toán này do nhà toán học cổ người Hy Lạp Eratosthenes (Ê-ra-tô-xten) phát minh ra.

Lịch sử của sàng Eratosthenes

Vào thế kỉ III TCN, ở Cyrene (Hy Lạp), nhà toán học cổ đại Eratosthenes đã phát minh một thuật toán để tìm các số nguyên tố, gọi là sàng Eratosthenes. Ban đầu, ông xếp 100 lá cọ tương ứng với 100 số tự nhiên từ 1 đến 100. Sau khi chọc thủng lá cọ số 1, ông giữ nguyên các số nguyên tố (các lá cọ chưa bị chọc thủng) và lần lượt chọc thủng các bội của chúng. Cuối cùng, thuật toán đã sàng lại những số nguyên tố và loại bỏ các số không phải số nguyên tố nên được gọi là sàng nguyên tố Eratosthenes.

Mô tả giải thuật

Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên $N$ bằng sàng Eratosthenes, ta làm như sau:

Hình minh họa cho thấy thuật toán đơn giản để tìm số nguyên tố và các bội số
Các số tô màu giống nhau là cùng một họ mà dẫn đầu (đậm hơn) sẽ là số nguyên tố

*Bước 1:* Tạo 1 danh sách các số tự nhiên liên tiếp từ 1 đến $N$: (1, 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ố (ngoại trừ số 1 không 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 của số nguyên tố $p$ như $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 $\backslash sqrt\; 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.

Cải tiến giải thuật:

Xét $X=k\; \backslash times\; p$ là bội của số nguyên tố $p$.

Nếu , ta có . Suy ra $k$ phải có một ước nguyên tố nhỏ hơn $p$. Vì thế, các bội $X=k\; \backslash times\; p$ () đã bị sàng Eratosthenes loại bỏ trong các vòng lặp trước đó và ta chỉ cần xét $X>=p^2$.

Cài đặt

Mã giả:

// Input: một số nguyên n > 1. // Cho A là một mảng boolean, được đánh số từ 0 đến n. // Gán tất cả phần tử trong mảng là true và gán A[0] := A[1] := false.

for i = 2, 3, 4,..., √n: if A[i] is true: for j = i², i²+i, i²+2i,..., n: A[]:= false