Pascal: Kiểm tra tính nguyên tố của một số

Được sửa bởi littlelee ngày Mon 08 Mar 2010, 12:02; sửa lần 1.

Đây có lẽ là một trong những bài dễ nhất của môn tin ^^. Tuy vậy, trong bài viết này, mình sẽ giải thích nhiều cách làm và nhiều cách thể hiện.

Số nguyên tố là số chỉ chia hết cho chính nó và cho 1 (chỉ tính số dương).

Cách 1:
Dựa vào đặc tính của số nguyên tố, ta sẽ có giải thuật đơn giản sau: Cho vòng lặp chạy từ 2 đến số vừa nhập trừ một, nếu số vừa nhập chia hết cho biến chạy của vòng lặp thì có nghĩa số vừa nhập không nguyên tố. Nói thế thì khó hiểu, hình dung nó thế này. Giả sử số vừa nhập vào là n, ta cho i chạy từ 2 đến n-1, nếu n chia hết cho i trong bất cứ lần lặp nào thì có nghĩa là n không nguyên tố, nếu không chia hết cho bất cứ lần lặp nào là nguyên tố. Minh họa bằng bài cụ thể:

Code:: program kiem_tra_nguyen_to;
uses crt;
var n,i:integer; bl:boolean;
begin
clrscr;
bl:=true;
write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
for i:=2 to n-1 then
if n mod i=0 then bl:=false;
if bl=true then write('so vua nhap nguyen to.')
else write('so vua nhap khong nguyen to.');
readln;
end.

Bổ sung cho cách 1

Với cách trên, ta thấy thuật toán rất đơn giản, dựa vào chính hoạt động bình thường để chuyển háo thành ngôn ngữ lập trình. Tuy nhiên, với thuật toán trên, ta sẽ có trường hợp đặc biệt mà máy tính sẽ cho ra kết quả không mong muốn. Ví dụ khi nhập số nhập vào là 2, máy sẽ chạy từ 2 đến 2-1=1, tức là ko chạy. Khi nhập vào là 0 hoặc 1, nó cũng ko chạy và dĩ nhiên, biến boolean bl sẽ vẫn giữ giá trị true, như vậy bài sẽ cho là nguyên tố, trái ngược với thực tế, 0 và 1 là không phải là số nguyên tố. Như vậy, ta cần có một số lệnh kiểm tra ban đầu trước khi vào vòng lặp. Ta sửa bài lại như sau:

Code:: program kiem_tra_nguyen_to;
uses crt;
var n,i:integer; bl:boolean;
begin
clrscr;
bl:=true;
write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
if n<=1 then bl:=false
else
for i:=2 to n-1 then
if n mod i=0 then bl:=false;
if bl=true then write('so vua nhap nguyen to.')
else write('so vua nhap khong nguyen to.');
readln;
end.

Sau khi sửa lại, bài sẽ cho kết quả đúng với mọi trường hợp ^^.

Được sửa bởi littlelee ngày Sat 06 Mar 2010, 22:15; sửa lần 1.

Cách 2:

Bản chất của cách 2 (và của mọi cách sau nữa) cũng chỉ là cải tiến lại cách cơ bản (cách 1) mà thôi. Dĩ nhiên, để cải tiến, ta cần có chút suy nghĩ.

Trong cách này, mình sẽ cải tiến phạm vi chạy của biến i. Để chứng mình giải thuật này ta sẽ lấy vài ví dụ nhé. Lấy ví dụ số không nguyên tố mới thấy được.

9=3*3
12=3*4
18=2*9=3*6
20=4*5=2*10
...

trong các ví dụ trên, các số không nguyên tố được phân tích thành tích các cặp ước của chúng, trong mỗi cặp số nhỏ đứng trước, số lớn đứng sau. Trong mỗi cặp, ta có thể thấy rõ một điều: số đứng trước (nhỏ hơn) luôn luôn nhỏ hơn hoặc bằng căn bậc hai của số cần xét. Ví dụ ta thấy 20=4*5, rõ ràng 4 nhỏ hơn căn bậc hai của 20. Bạn tự xét các ví dụ khác nhé. Có thẻ chứng minh được điều này bằng toán học.

Chứng minh:
Gọi số cần xét là n, căn bậc hai của nó là x, hai ước tương ứng có tích bằng n của nó là a và b(a<>b), ta cần chứng minh a<x hoặc b<x. Vì a và b có vai trò tương đương, nên ta giả sử a<b.
Giả sử a>x và b>x, ta có a*b>x*x=n => trái với giải thiết. Vậy trong hai số a và b, phải có một số nhỏ hơn x.

Dựa vào đặc điểm trên, ta sẽ giới hạn phạm vi của i là 2>n-1 thành 2->sqrt(n). Tuy nhiên, sqrt(n) với n không chính qhuwowng sẽ ra số vô tỉ, trong khi i là số nguyên, vậy cần làm tròn sqrt(n). Phạm vi mới sẽ là 2->trunc(sqrt(n)).

Code:: program kiem_tra_nguyen_to;
uses crt;
var n,i:integer; bl:boolean;
begin
clrscr;
bl:=true;
write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
if n<=1 then bl:=false;
for i:=2 to trunc(sqrt(n)) then
if n mod i=0 then bl:=false;
if bl=true then write('so vua nhap nguyen to.')
else write('so vua nhap khong nguyen to.');
readln;
end.

Được sửa bởi littlelee ngày Sat 06 Mar 2010, 22:13; sửa lần 1.

Cách 3

Ở cách này, ta tiếp tục cải tiến phạm vi của biến chạy i.

Ta xét một ví dụ đơn giản sau của cách 2 (cách đã có cải tiến).

n=1600
=> trunc(sqrt(n))=40
i chạy từ 2->40, khi đó i có đến 20 lần mang giá trị chẵn.

Như ta đã biết, mọi số chẵn lớn hơn 2 đều là hợp số. Chính vì thế, việc kiểm tra đối với số chẵn chỉ cần kiểm tra nó có chẵn hay ko đã là đủ. Đối với số lẻ, ta lại thấy, nó không bao giwof chia hết cho số chẵn, vậy việc biến i chạy trên các giả trị chẵn là vô ích. Ta sẽ lược bỏ các giá trị chẵn này đi, tức là ko dùng vòng for mà dùng vòng while để mỗi lần chạy, ta cộng vào i 1 giá trị thích hợp, khớp với giá trị ban đầu để i ko mang giá trị chẵn. Ở cách này, mình đã loại trừ các trường hợp đặc biệt rồi.

Code:: program kiem_tra_nguyen_to;
uses crt;
var n,i:integer; bl:boolean;
begin
clrscr;
bl:=true;
write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
if (n<=1)or(n mod 2=0) then bl:=false;
if n>3 then
if n mod 2 =0 then bl:=false
else
begin
i:=3;
while i<=trunc(sqrt(n)) do
begin
if n mod i=0 then bl:=false;
i:=i+2;
end;
end;
if bl=true then write('so vua nhap nguyen to.')
else write('so vua nhap khong nguyen to.');
readln;
end.

Với cách thứ ba như trên, việc kiểm tra số nguyên tố của bạn đã đạt đến tốc độ khủng rồi đấy!

Bây giờ, mình sẽ trình bày bài toán này thành một hàm, mang tên ktnt (Kiểm Tra Nguyên Tố) để các bạn dễ dùng và thử (ví dụ in ra 10 000 số nguyên tố chẳng hạn để kiểm tra tốc độ). Trong phần này, mình gia tăng phạm vi của n lên longint để việc kiểm tra được nhiều hơn.

Code:: program kiem_tra_nguyen_to;
uses crt;
var n:longint;

function ktnt(n:longint):boolean;
var i:longint; bl:boolean;
begin
if (n<=1)or(n mod 2=0) then bl:=false;
if n>3 then
if n mod 2=0 then bl:=false
else
begin
i:=3;
while i<=trunc(sqrt(n)) do
begin
if n mod i=0 then bl:=false;
i:=i+2;
end;
end;
ktnt:=bl;
end;

begin
clrscr;
bl:=true;
write('nhap vao so can kiem tra tinh nguyen to: '); readln(n);
if ktnt(n) then write('so vua nhap nguyen to.')
else write('so vua nhap khong nguyen to.');
readln;
end.

Bài này tốt đấy. Bạn cố gắng tiếp tục nhé. Ít bữa, mình hỏi abnj tí, bạn nhớ giúp nhé.

OK, sẵn sàng 100%

Bài này có thể dùng thuật toán sàng số nguyên tố n<=200000.

Code:: Var A,B,i,j:longint;
F:Array[1..200000] of boolean;
BEGIN
Readln(A,B);
Fillchar(F,SiZeof(F),True);
F[1]:=False;
For i:=1 to B do
If F[i] then
Begin
j:=i+i;
While (j<=B) do
Begin
F[j]:=False;
j:=j+i;
End;
End;
For i:=A to B do
If F[i] then Writeln(i);
END.

Thuật toán kiểm tra số nguyên tố: Rabin Miller:

Code:: PROGRAM
Rabin_Miller_Algorithm;
CONST
tfi='rm.inp';
tfo='rm.out';
k=30;
VAR
n:int64;
LT:array[0..33]of int64;
fi,fo:text;

Procedure Init;
Var tg:int64;
i:longint;
Begin
tg:=1; LT[0]:=1;
for i:=1 to 33 do
begin
tg:=tg*2;
LT[i]:=tg;
end;
End;

Function Power(a,q,n:int64):int64;
Var c,p2,u:int64;
Begin
c:=1; u:=a; p2:=1;
repeat
if q and p2<>0 then c:=(c*u) mod n;
p2:=p2 shl 1;
u:=(u*u) mod n;
until p2>q;
Power:=c;
End;

Function MillerTest(n,a,q,t:int64):Boolean;
Var pre,c:int64;
i:longint;
Begin
c:=Power(a,q,n);
pre:=n-1;
for i:=0 to t do
begin
if c=1 then exit(pre=n-1);
pre:=c;
c:=(c*c) mod n;
end;
MillerTest:=False;
End;

Procedure Cal(n:int64; var q,t:int64);
Var i:longint;
Begin
for i:=0 to 33 do
if ((n-1) mod LT[i]=0) and (((n-1) div LT[i]) mod 2<>0) then
begin
q:=(n-1) div LT[i];
t:=i;
exit;
end;
End;

Function Prime(n:int64):Boolean;
Var i:longint;
a,q,t:int64;
Begin
Prime:=False;
if n=2 then exit(true);
if n mod 2=0 then exit(false);
Cal(n,q,t);
For i:=1 to k do
Begin
a:=random(n-1)+1;
if MillerTest(n,a,q,t)=false then exit;
End;
Prime:=True;
End;

Procedure OpenFile;
Begin
assign(fi,tfi); reset(fi);
assign(fo,tfo); rewrite(fo);
End;

Procedure Process;
Var i,test:longint;
Begin
read(fi,test);
for i:=1 to test do
begin
read(fi,n);
if Prime(n) then writeln(fo,n,' là số nguyên tố') else
writeln(fo,n,' không phai là số nguyên tố');
end;
End;

Procedure CloseFile;
Begin
close(fi); close(fo);
End;

Procedure RM;
Begin
OpenFile;
Init;
Process;
CloseFile;
End;

BEGIN
RM;
END.

Gà mờ Tổng số bài gửi : 1 Join date : 22/04/2011

sao em làm theo cách 1 và cách 2 đều không chạy được ?

» "Ông thầy nóng tính" trích"Kính vạn hoa" của Nguyễn Nhật Ánh
» Nhờ các bạn mấy bài Pascal
» Bài tập pascal về tệp cần giải gấp!!!
» Bản kiểm điểm
» Các nhà vật lý tìm kiếm vật chất tối ( sưu tầm đấy)