Sàng Eratosthenes
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Portrait_of_Eratosthenes.png/200px-Portrait_of_Eratosthenes.png)
Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố trong khoảng 100 số tự nhiên. 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.
Hình thức của sàng Eratosthenes
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.[cần dẫn nguồn]
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:
![](http://upload.wikimedia.org/wikipedia/commons/b/b8/Animation_Sieb_des_Eratosthenes_%28vi%29.gif)
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ừ 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.
Cài đặt
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
Lúc này, tất cả i ví dụ như của A[i] nếu true đều là số nguyên tố.
Tham khảo
![]() | Bài viết liên quan đến toán học này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.
|