Thuật toán sàng nguyên tố Eratosthenes là một công cụ mạnh mẽ để giải quyết những bài toán đòi hỏi phải kiểm tra số nguyên tố nhiều lần. 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ố.

Thuật toán:
Dùng 1 mảng bool có N phần tử, với giá trị khởi tạo cho các phần tử của mảng đều là True, với ý nghĩa các số từ 1..N đều là số nguyên tố.
Gán a[1]=false (1 không phải là số nguyên tố);
B1: i++ cho đến khi a[i]= true;
B2: Điền các phần tử của mảng a có chỉ số là 2*i, 3*i… là false (với ý nghĩa các số này ko phải là số nguyên tố)
B3:Nếu i*i>=N thoát chương trình, nếu không quay lại bước 1.

pseudocode:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., while in/2:
  if A[i] is true:
    for j = 2i, 3i, 4i, ..., while jn:
      A[j] = false

Now all i such that A[i] is true are prime.

Ngoài ra bạn có thê tham khảo công cụ mạnh hơn (nhưng cài đặt cũng phức tạp hơn) đó là sàng Atkin.

Advertisements