Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập
Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi: 415
Join date: 20/12/2009
Age: 19
Đến từ: Nghĩa địa

Bài gửiTiêu đề: Pascal: Kiểm tra tính nguyên tố của một số   Sat 06 Mar 2010, 15:17

Đâ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 Mon 08 Mar 2010, 12:02; sửa lần 1.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi: 415
Join date: 20/12/2009
Age: 19
Đến từ: Nghĩa địa

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Sat 06 Mar 2010, 21:51

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:15; sửa lần 1.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi: 415
Join date: 20/12/2009
Age: 19
Đến từ: Nghĩa địa

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Sat 06 Mar 2010, 22:04

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.


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


Tổng số bài gửi: 415
Join date: 20/12/2009
Age: 19
Đến từ: Nghĩa địa

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Sat 06 Mar 2010, 22:12

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.
Về Đầu Trang Go down
vankhoa1260
Gà con


Tổng số bài gửi: 19
Join date: 09/02/2010
Age: 19
Đến từ: Thiên Đường

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Mon 08 Mar 2010, 18:50

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é.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi: 415
Join date: 20/12/2009
Age: 19
Đến từ: Nghĩa địa

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Mon 08 Mar 2010, 19:34

OK, sẵn sàng 100%
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi: 101
Join date: 25/07/2010
Age: 20
Đến từ: Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Mon 26 Jul 2010, 15:58

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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


Tổng số bài gửi: 101
Join date: 25/07/2010
Age: 20
Đến từ: Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Mon 26 Jul 2010, 16:46

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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
bafalabafala
Gà mờ


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

Bài gửiTiêu đề: Re: Pascal: Kiểm tra tính nguyên tố của một số   Fri 22 Apr 2011, 19:30

sao em làm theo cách 1 và cách 2 đều không chạy được ?
Về Đầu Trang Go down
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

 Similar topics

-
» Trai TÂY NGUYÊN bắt côn trùng bỏ vào dương vật và tinh hoàn
» Kiếm em trai 13 - 18 tuổi !!!!!!!!
» Callboy can tho body dep.kiem khach can tho 30t tro len.0932895811
» Cho bú cu tai Nguyễn Thái Sơn Gò Vấp
» [MF] tài nguyên RPG maker VX

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh ::  :: -