SÀNG NGUYÊN TỐ ERATOSTHENES

Trích: Sáng tạo trong thuật toán và lập trình (Quyển 2)

Từ thời cổ xưa, Eratosthenes đã dạy các học trò của mình như sau:

Muốn liệt kê toàn bộ số nguyên tố từ 1..N, hãy làm như sau:

Trước tiên, viết dãy số từ 1..N

Xóa số 1, vì đó là số đặc biệt, không phải số nguyên tố cũng không phải hợp số

Duyệt từ 2 tới Căn(N). Nếu gặp số nào chưa bị xóa đi thì đólà số nguyên tố và lần lượt xóa các bội số của số này kể từ bình phương của nó trở đi.

Khi kết thúc, nhưng số chưa bị xóa chính là số nguyên tố

thủ tục Sàng nguyên tố:

1. Fillchar(P, sizeof(P), 0);
2. For i:=2 to round(SQRT(N)) do
3. If P[i]=0 then
4. For j:=i to (n div i) do P[i*j]:=1;