Viết chương trình Pascal nhập vào một số nguyên n, kiểm tra n có phải là số nguyên tố hay không. Giải thích thuật toán.

Question

Timi · Accepted Answer

Dưới đây là chương trình Pascal nhập vào một số nguyên n, kiểm tra xem n có phải là số nguyên tố hay không, kèm theo giải thích thuật toán:

```pascal
program KiemTraSoNguyenTo;
uses crt;
var
  n, i: integer;
  isPrime: boolean;
begin
  clrscr;
  write(&#x27;Nhap vao so nguyen n: &#x27;);
  readln(n);

if n < 2 then
    isPrime := false
  else
  begin
    isPrime := true;
    // Kiểm tra từ 2 đến căn bậc hai của n
    for i := 2 to trunc(sqrt(n)) do
    begin
      if n mod i = 0 then
      begin
        isPrime := false;
        break; // Nếu tìm thấy ước số thì dừng vòng lặp
      end;
    end;
  end;

if isPrime then
    writeln(n, &#x27; la so nguyen to.&#x27;)
  else
    writeln(n, &#x27; khong phai la so nguyen to.&#x27;);

readln;
end.
```

**Giải thích thuật toán:**

- Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
- Nếu n < 2 thì n không phải số nguyên tố.
- Để kiểm tra n có phải số nguyên tố hay không, ta chỉ cần kiểm tra xem n có chia hết cho số nào từ 2 đến căn bậc hai của n hay không.
- Nếu tìm thấy một số i trong khoảng này mà n chia hết cho i (n mod i = 0), thì n không phải số nguyên tố.
- Nếu không tìm thấy số nào chia hết, thì n là số nguyên tố.
- Việc chỉ kiểm tra đến căn bậc hai của n giúp giảm số lần kiểm tra, tăng hiệu quả thuật toán.