Chương trình Pascal bảng số nguyên tố

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.