Phương pháp Sàng Eratosthenes

Sàng Eratosthenes là phương pháp toán học cổ đại dùng để xác định các số nguyên tố trong một dãy số từ 1 đến 100. Phương pháp này được nhà toán học Hy Lạp cổ đại Eratosthenes phát minh.

Đặc điểm của phương pháp Sàng Eratosthenes

Khi phát minh ra thuật toán, Eratosthenes đã viết tất cả các số từ 2 đến 100 lên các lá cọ. Ông gạch bỏ các hợp số và giữ lại các số nguyên tố, tạo nên một bảng số rất giống như cái sàng, vì thế phương pháp được gọi là sàng Eratosthenes.

Thuật toán

Để xác định các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng phương pháp Sàng Eratosthenes, thực hiện các bước sau:

• Bước 1: Tạo một danh sách các số liên tiếp từ 2 đến n: (2, 3, 4,..., n).
• Bước 2: Giả định tất cả các số trong danh sách là số nguyên tố. Bắt đầu với p = 2, số nguyên tố đầu tiên.
• Bước 3: Đánh dấu tất cả các bội số của p: 2p, 3p, 4p,... vì chúng không phải là số nguyên tố.
• Bước 4: Tìm các số chưa bị đánh dấu trong danh sách, lớn hơn p và nhỏ hơn hoặc bằng căn bậc hai của n. Nếu không còn số nào, kết thúc. Nếu còn, gán p bằng số nguyên tố tiếp theo và lặp lại bước 3.

Khi thuật toán hoàn tất, tất cả các số chưa bị đánh dấu trong danh sách đều là số nguyên tố cần tìm.

Thiết lập

mã giả:

 
Dữ liệu đầu vào: một số nguyên n > 1
Cho A là mảng boolean, đánh số từ 2 đến n,
khởi tạo với tất cả các phần tử đều là true.
 
for i = 2, 3, 4,..., √n:
if A[i] là true:
for j = i, i+i, i+2i,..., n:
A[j]:= false

 
Cuối cùng, tất cả i mà A[i] vẫn là true đều là các số nguyên tố.