Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là true

Thuật toán kiểm tra số nguyên tố trong pascal của ta dựa trên ý tưởng: nếu n >1 không chia hết cho số nguyên nào trong tất cả các số từ 2 đến thì n là số nguyên tố. Do đó ta sẽ kiểm tra tất cả các số nguyên từ 2 đến có round(sqrt(n)), nếu n không chia hết cho số nào trong đó thì n là số nguyên tố.

Nếu thấy biểu thức round(sqrt(n)) khó viết thì ta có thể kiểm tra từ 2 đến n div 2.

Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là true (đúng) nếu n là nguyên tố và trả lại false nếu n không là số nguyên tố

Bài giải

program sont;

uses crt;
var n,i,tong,j:integer;
    snt:boolean;
    A:array[1..100] of integer;
function ktnt(a:integer):boolean;
    var i:integer;
    kt:boolean;
    begin
    kt:=true;
    if a<=1 then kt:=false;
    for i:=2 to trunc(sqrt(a)) do
    if (a mod i = 0) then kt:=false;
    ktnt:=kt;
    end;

begin
clrscr;
writeln('nhap so phan tu cua mang A :');
readln(n);
for i:= 1 to n do
    begin
    writeln('nhap phan tu thu ',i,' ');
    read(A[i]);
    end;
tong:=0;
for i:=1 to n do
begin
if ktnt(A[i]) then
   tong:=tong+1;
end;
writeln('-------------------------------------------');
writeln(' tong co ',tong,' snt trong mang' );
writeln(' cac so do la ');
for i:=1 to n do
if ktnt(A[i]) then write(A[i],' ');
readln;
readln;
end.