Sàng nguyên tố (hay còn gọi là Sàng Eratosthenes) là một thuật toán được sử dụng để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n cho trước. Thuật toán này được đặt theo tên của nhà toán học Eratosthenes, người đã phát hiện ra cách tìm số nguyên tố bằng cách sàng.
Dưới đây là mã Pascal để hiện thực thuật toán sàng nguyên tố:
procedure SieveOfEratosthenes(n: Integer);
var
prime: array[2..n] of Boolean;
i, j: Integer;
begin
for i := 2 to n do
prime[i] := True;
for i := 2 to Trunc(Sqrt(n)) do
begin
if prime[i] then
begin
j := i * i;
while j <= n do
begin
prime[j] := False;
j := j + i;
end;
end;
end;
for i := 2 to n do
begin
if prime[i] then
WriteLn(i);
end;
end;
Giải thích:
prime
là một mảng Boolean lưu trữ thông tin về số nguyên tố. Ban đầu, tất cả các phần tử của mảng đều được thiết lập làTrue
.- Vòng lặp đầu tiên từ 2 đến n được sử dụng để thiết lập tất cả các giá trị ban đầu của
prime
làTrue
. - Vòng lặp thứ hai từ 2 đến căn bậc hai của n được sử dụng để loại bỏ các số không phải số nguyên tố. Nếu
prime[i]
làTrue
, thì ta biết rằng i là số nguyên tố, vì vậy ta sẽ loại bỏ tất cả các bội số của i (từ i * i đến n) bằng cách thiết lập giá trị tương ứng củaprime
thànhFalse
. - Vòng lặp cuối cùng từ 2 đến n được sử dụng để hiển thị tất cả các số nguyên tố được tìm thấy. Nếu
prime[i]
làTrue
, thì i là số nguyên tố và ta in nó ra.
Dưới đây là một ví dụ cụ thể về cách cài đặt thuật toán sàng nguyên tố trong ngôn ngữ lập trình Pascal:
program SieveOfEratosthenes;
const
MAX = 1000000;
var
primes: array[2..MAX] of Boolean;
i, j, n: Integer;
begin
Write('Nhap n: ');
ReadLn(n);
// Khởi tạo mảng primes ban đầu là True
for i := 2 to n do
primes[i] := True;
// Loại bỏ các bội số của các số nguyên tố
for i := 2 to Trunc(Sqrt(n)) do
begin
if primes[i] then
begin
j := i * i;
while j <= n do
begin
primes[j] := False;
j := j + i;
end;
end;
end;
// In ra các số nguyên tố
WriteLn('Cac so nguyen to nho hon hoac bang ', n, ':');
for i := 2 to n do
begin
if primes[i] then
Write(i, ' ');
end;
end.
Giải thích:
- Đầu tiên, chương trình yêu cầu người dùng nhập vào giá trị của n.
- Sau đó, mảng primes được khởi tạo với tất cả các giá trị ban đầu là
True
, ngoại trừ primes[1] = False (1 không phải số nguyên tố). - Chương trình duyệt qua các số nguyên tố từ 2 đến căn bậc hai của n và loại bỏ các bội số của chúng bằng cách thiết lập giá trị tương ứng trong mảng primes thành
False
. - Cuối cùng, chương trình in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n.