Sàng nguyên tố trong Pascal

Sàng nguyên tố (hay còn gọi là Sàng Eratosthenes) là một thuật toán được sử dụng để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên dương n cho trước. Thuật toán này được đặt theo tên của nhà toán học Eratosthenes, người đã phát hiện ra cách tìm số nguyên tố bằng cách sàng.

Dưới đây là mã Pascal để hiện thực thuật toán sàng nguyên tố:

procedure SieveOfEratosthenes(n: Integer);
var
  prime: array[2..n] of Boolean;
  i, j: Integer;
begin
  for i := 2 to n do
    prime[i] := True;

  for i := 2 to Trunc(Sqrt(n)) do
  begin
    if prime[i] then
    begin
      j := i * i;
      while j <= n do
      begin
        prime[j] := False;
        j := j + i;
      end;
    end;
  end;

  for i := 2 to n do
  begin
    if prime[i] then
      WriteLn(i);
  end;
end;

Giải thích:

prime là một mảng Boolean lưu trữ thông tin về số nguyên tố. Ban đầu, tất cả các phần tử của mảng đều được thiết lập là True.
Vòng lặp đầu tiên từ 2 đến n được sử dụng để thiết lập tất cả các giá trị ban đầu của prime là True.
Vòng lặp thứ hai từ 2 đến căn bậc hai của n được sử dụng để loại bỏ các số không phải số nguyên tố. Nếu prime[i] là True, thì ta biết rằng i là số nguyên tố, vì vậy ta sẽ loại bỏ tất cả các bội số của i (từ i * i đến n) bằng cách thiết lập giá trị tương ứng của prime thành False.
Vòng lặp cuối cùng từ 2 đến n được sử dụng để hiển thị tất cả các số nguyên tố được tìm thấy. Nếu prime[i] là True, thì i là số nguyên tố và ta in nó ra.

Dưới đây là một ví dụ cụ thể về cách cài đặt thuật toán sàng nguyên tố trong ngôn ngữ lập trình Pascal:

program SieveOfEratosthenes;

const
  MAX = 1000000;

var
  primes: array[2..MAX] of Boolean;
  i, j, n: Integer;

begin
  Write('Nhap n: ');
  ReadLn(n);

  // Khởi tạo mảng primes ban đầu là True
  for i := 2 to n do
    primes[i] := True;

  // Loại bỏ các bội số của các số nguyên tố
  for i := 2 to Trunc(Sqrt(n)) do
  begin
    if primes[i] then
    begin
      j := i * i;
      while j <= n do
      begin
        primes[j] := False;
        j := j + i;
      end;
    end;
  end;

  // In ra các số nguyên tố
  WriteLn('Cac so nguyen to nho hon hoac bang ', n, ':');
  for i := 2 to n do
  begin
    if primes[i] then
      Write(i, ' ');
  end;
end.

Giải thích:

Đầu tiên, chương trình yêu cầu người dùng nhập vào giá trị của n.
Sau đó, mảng primes được khởi tạo với tất cả các giá trị ban đầu là True, ngoại trừ primes[1] = False (1 không phải số nguyên tố).
Chương trình duyệt qua các số nguyên tố từ 2 đến căn bậc hai của n và loại bỏ các bội số của chúng bằng cách thiết lập giá trị tương ứng trong mảng primes thành False.
Cuối cùng, chương trình in ra tất cả các số nguyên tố nhỏ hơn hoặc bằng n.

Lập trình Pascal

Sàng nguyên tố trong Pascal

Trả lời Hủy