Học Pascal/Ứng dụng vào bài toán

Tủ sách mở Wikibooks
Bước tới điều hướng Bước tới tìm kiếm

Tìm các số nguyên tố không vượt quá N (N < 255)[sửa]

Định nghĩa số nguyên tố: Là số tự nhiên chỉ chia hết cho 1 và chính nó (không bao gồm số 1).

Cách 1[sửa]

Mô tả[sửa]

Chương trình[sửa]

PROGRAM Loc;
USES crt;
VAR Tapnguyento: SET OF Byte;
    i, j, N: Integer;
    dem: Byte
BEGIN
  clrscr;
  Write('Hay nhap so N khong vuot qua 255 :');
  REPEAT Readln(N) UNTIL N in [2..255];
  Tapnguyento:= []; dem:= 0;
  FOR i:=2 to N DO
    BEGIN
      FOR j:=1 to i do
        IF (i mod j = 0) THEN dem:= dem + 1;
      IF (dem = 2) THEN Tapnguyento:= Tapnguyento + [i];
      dem:= 0;
    END;
  clrscr;
  Writeln('Cac so nguyen to nho hon ',N);
  FOR i:= 2 TO N DO
    IF i in Tapnguyento THEN Write(i:4);
  Readln
END.

Cách 2 - Sử dụng giải thuật "sàng Eratosthenes"[sửa]

Kiểu áp dụng: Học Pascal/Tập hợp Áp dụng: Học Pascal/Vòng lặp

Mô tả[sửa]

  • Bước 1: Tập các số chưa xét được gán là [2..N]. Tập các số nguyên tố được gán là rỗng [].
  • Bước 2: Tìm số bé nhất chưa xét. Số đó chính là số nguyên tố mới tìm được.
  • Bước 3: Ghi nhận số nguyên tố vừa tìm vào tập các số nguyên tố. Sàng đi (loại bỏ) từ tập các số chưa xét mọi bội số của số nguyên tố đó (kể cả nó).
  • Bước 4: Nếu tập các số chưa xét khác rỗng thì quay lại bước 2, nếu rỗng thì sang bước 5.
  • Bước 5: Cho ra tập các số nguyên tố.
Ví dụ với N = 10, thuật toán hoạt động như sau
Bước Tập các số chưa xét Số tìm được Tập các số nguyên tố Chú thích
1 [2, 3, 4, 5, 6, 7, 8, 9, 10] [] Tập các số chưa xét được gán là [2..N]. Tập các số nguyên tố được gán là rỗng []
2 [2, 3, 4, 5, 6, 7, 8, 9, 10] 2 [] Tìm số bé nhất chưa xét (2)
3 [3, 5, 7, 9] [2] Ghi số tìm được vào tập các số nguyên tố, loại bỏ bội của số đó (2) từ tập các số chưa xét (loại bỏ 2, 4. 6, 8)
4 [3, 5, 7, 9] [2] Tập các số chưa xét khác rỗng, quay lại bước 2
2 [3, 5, 7, 9] 3 [2] Tìm số bé nhất chưa xét (3)
3 [5, 7] [2, 3] Ghi số tìm được vào tập các số nguyên tố, loại bỏ bội của số đó (3) từ tập các số chưa xét (loại bỏ 3, 9)
4 [5, 7] [2,3] Tập các số chưa xét khác rỗng, quay lại bước 2
2 [5, 7] 5 [2, 3]
3 [7] [2, 3, 5]
4 [7] [2, 3, 5]
2 [7] 7 [2, 3, 5]
3 [] [2, 3, 5, 7]
4 [] 7 [2, 3, 5, 7] Tập các số chưa xét rỗng chuyển xuống bước 5

Chương trình[sửa]

PROGRAM Sang;
USES crt;
VAR Tapchuaxet, Tapnguyento: SET OF Byte;
    N, J, Sotiep: Integer;
BEGIN
  clrscr;
  Write('Hay nhap so N khong qua 255: ');
  REPEAT Readln(N) UNTIL N in [2..255];
  Tapchuaxet:= [2..N];  Tapnguyento:= [];   {Buoc 1}
  Sotiep:= 2;
  REPEAT                {buoc 4}
     WHILE (Sotiep <= N) AND NOT (Sotiep in Tapchuaxet) DO       {Buoc 2}
       Sotiep:= Sotiep + 1;                                {tim so nguyen to tiep theo}
     Tapnguyento:= Tapnguyento + [Sotiep];    {Buoc 3}
     J:= Sotiep;
     WHILE (J <= N) DO
       BEGIN
         Tapchuaxet:= Tapchuaxet - [J];  {loai bo so tim duoc va boi cua no khoi tap chua xet}
         J:= J + Sotiep;
        END;
  UNTIL Tapchuaxet = [];                  {Buoc 4}
  clrscr;
  Writeln('Cac so nguyen to nho hon ',N,' la');
  FOR J:=2 TO N DO
    IF J in Tapnguyento THEN Write(J:4);       {Buoc 5}
  Readln
END>