prime-number-1.pas
(* ==================================================================
Prime Numbers -- Số Nguyên Tố
In tất cả các số nguyên tố trong khoảng 2..MaxNum
Cách giải: Cho n chạy từ 2 đến MaxNum. Kiểm tra xem n có phải là
số nguyên tố không. Nếu đúng thì in ra giá trị của n. Cách kiểm
tra là cho i chạy từ 2 đến sqrt(n) và kiểm tra xem n có chia hết
cho i không (n mod i ?= 0). Nếu chia hết cho một i nào đó thì n
không phải là số nguyên tố.
16-12-2008 triplc [at] gmail [dot] com
================================================================== *)
program PrimeNumbers;
const NumberPerRow = 6; (* số các số mỗi dòng in *)
NumberWidth = 8; (* độ rộng của từng số *)
var MaxNum : longint; (* dải các số cần tìm: 2..MaxNum *)
n : longint; (* số đang được kiểm tra *)
i : longint; (* phép kiểm tra n mod i = 0 *)
PrimeFound : longint; (* số các số nguyên tố đã tìm được *)
IsPrime : boolean; (* n có phải là số nguyên tố không *)
begin
(* in tiêu đề chương trình *)
WriteLn ('=================================================');
WriteLn (' Prime Number ');
WriteLn ('=================================================');
WriteLn;
(* đọc MaxNum *)
Write ('MaxNum =? '); ReadLn (MaxNum); WriteLn;
(* hiện nay mới tìm được 0 số nguyên tố *)
PrimeFound := 0;
(* kiểm tra tất cả các số từ 2 đến MaxNum *)
for n := 2 to MaxNum do begin
if (n <= 3) then
(* n=2 và n=3 hiển nhiên là số nguyên tố *)
IsPrime := True
else begin
(* kiểm tra xem n có chia hết cho i không, với mọi i*i<=n *)
for i := 2 to Trunc (Sqrt (n)) do
if (n mod i = 0) then break;
(* n là số nguyên tố nếu n không chia hết cho i *)
IsPrime := (n mod i <> 0);
end;
(* nếu n là số nguyên tố, thì ..... *)
if IsPrime then begin
(* in ra n *)
Write (n:NumberWidth);
(* tăng giá trị số đếm PrimeFound lên 1 đơn vị *)
PrimeFound := PrimeFound + 1;
(* in dấu xuống dòng mỗi khi in NumberPerRow số nguyên tố *)
if (PrimeFound mod NumberPerRow = 0) then WriteLn;
end;
end;
(* in phần kết của chương trình *)
WriteLn;
WriteLn;
WriteLn ('Found ', PrimeFound, ' prime numbers in range 2..', MaxNum);
WriteLn;
WriteLn ('=================================================');
end.
prime-number-2.pas
(* ==================================================================
Prime Numbers -- Số Nguyên Tố
In tất cả các số nguyên tố trong khoảng 2..MaxNum
Thuật giải "Sieve of Eratosthenes"
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Prime_number
Diễn giải: Ban đầu giả sử tất cả các số từ 2 đến MaxNum đều là số
nguyên tố. Sau đó loại ra tất cả các số nào không phải là số
nguyên tố: tất cả bội số của 2, 3, 5... Ban đầu xét n=2, và thấy
không bị loại (tức là n=2 là số nguyên tố), vậy ta loại tất cả bội
của 2. Sau đó kiểm tra n=3, thấy chưa bị loại, vậy n=3 là số nguyên
tố (vì nó không phải là bội của bất kỳ số nào nhỏ hơn nó), và ta
loại tất cả bội của 3. Kiểm tra n=4 thì thấy đã bị loại (vì là bội
số của 2), vậy bỏ qua. Kiểm tra với n=5, v.v. Đến khi loại hết tất
cả các bội số của n với n <= sqrt(MaxNum) thì xong.
16-12-2008 triplc [at] gmail [dot] com
================================================================== *)
program PrimeNumbers;
const MaxNum = 1000; (* dải các số cần tìm: 2..MaxNum *)
NumberPerRow = 6; (* số các số mỗi dòng in *)
NumberWidth = 8; (* độ rộng của từng số *)
var IsPrime : array [2..MaxNum] of boolean;
(* n có phải là số nguyên tố không *)
i,n : longint; (* biến đếm *)
PrimeFound : longint; (* số các số nguyên tố đã tìm được *)
begin
(* khởi tạo IsPrime, giả sử tất cả đều là số nguyên tố *)
for i := 2 to MaxNum do IsPrime[i] := True;
(* cho n chạy từ 2 đến sqrt(MaxNum);
n là giá trị cho biết rằng tất cả các IsPrime[i] với
2 <= i <= n đều đã confirm đúng là số nguyên tố hay không *)
for n := 2 to Trunc (Sqrt (MaxNum)) do
(* nếu n không phải số nguyên tố thì không làm gì cả
còn nếu n là số nguyên tố thì tất cả các bội số của n
đều bị loại khỏi danh sách các số nguyên tố. Chỉ cần
xác định các bội n*i với i>=n *)
if IsPrime[n] then
for i := n to Trunc (MaxNum / n) do
IsPrime[n*i] := False;
(* in tiêu đề chương trình *)
WriteLn ('=================================================');
WriteLn (' Prime Number ');
WriteLn ('=================================================');
WriteLn;
(* hiện nay mới đếm được 0 số nguyên tố *)
PrimeFound := 0;
(* duyệt tất cả các số từ 2 đến MaxNum *)
for n := 2 to MaxNum do begin
(* nếu n là số nguyên tố, thì ... *)
if IsPrime[n] then begin
(* in ra n *)
Write (n:NumberWidth);
(* tăng giá trị số đếm PrimeFound lên 1 đơn vị *)
PrimeFound := PrimeFound + 1;
(* in dấu xuống dòng mỗi khi in NumberPerRow số nguyên tố *)
if (PrimeFound mod NumberPerRow = 0) then WriteLn;
end;
end;
(* in phần kết của chương trình *)
WriteLn;
WriteLn;
WriteLn ('Found ', PrimeFound, ' prime numbers in range 2..', MaxNum);
WriteLn;
WriteLn ('=================================================');
end.
