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

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

Đị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

Chương trình

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"

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

Mô tả

• 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

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>