Gợi ý dùng Sàng Eratosthene là 1 mảng bolean từ 2 dến N . thuật toán mô tả như sau:
Eratosthene(n)
Var List Prime[1..n] of boolean;
i,j,k : kiểu nguyên
for i:=1 to n Prime[i]:=True
Prime[1]:=false
k=0
while k < sqrt(n) do
begin
i=k+1;
while Prime[i]=False do i:=i+1
k:=i
j:=2
while k*j<=n
begin
Prime[k*j]:= False
j:=j+1
end;
end;
end