Chương trình con kiểm tra 1 số có là số nguyên tố hay không

**lehang_gb1** · 04-07-2009 22:01

Các bạn hãy viết các cách để kiểm tra 1 số có là số nguyên tố hay không (dùng chương trình con.
Trong nhiều sách mình thấy dùng hàm sau nhưng mình chạy với số 1 thì in ra là số nguyên tố. Các bạn đọc và cho ý kiến nhé
Function ngto(N:integer):Boolean;
Var i:integer;
Begin
ngto:=false;
For i:=2 to trunc(sqrt(N)) do
if N mod i = 0 then exit;
ngto:=true;
End;

**mr_invincible** · 04-07-2009 23:32

Thay dòng ngto:=true; bằng dòng ngto:=N>1; (đoạn chương trình trên chỉ kiểm tra xem 1 số có ước khác 1 và chính nó ko)

**lehang_gb1** · 05-07-2009 14:25

Mình đã hiểu vì sao đoạn CTC trên chạy lại cho kết quả 1 là số nguyên tố vì với N=1 ban đầu ngto:=false
Sau đó thì vòng for không được thực hiện vì i chạy từ 2 đến... vì vậy không có lệnh Exit thoát khỏi chương trình con. Và cuối cùng hàm ngto lại gán bằng true ngto:=true. Vậy 1 sẽ là số nguyên tố. Cần sửa lại như bạn mr_invincible là đúng. Thanks

**lehang_gb1** · 13-07-2009 22:55

Code:

Function ngto(N:integer):Boolean;
Var d,i:integer;
Begin
  d:=0;
     For i:=1 to n do
       If n mod i=0 then inc(d);
     if d=2 then ngto:=true
     else ngto:=false;
End;

Cách này kiểm tra được cả số 1. Nhưng cách này thời gain thực hiện sẽ lâu

**bld** · 14-07-2009 07:16

nói thật đến bây giờ mình vẫn chưa biết cài đặt sàng số nguyên tố sao cho tốt , bạn nào cho ý tưởng đi

**hang_vt** · 14-07-2009 08:30

Được gửi bởi lehang_gb1

Các bạn hãy viết các cách để kiểm tra 1 số có là số nguyên tố hay không (dùng chương trình con.
Trong nhiều sách mình thấy dùng hàm sau nhưng mình chạy với số 1 thì in ra là số nguyên tố. Các bạn đọc và cho ý kiến nhé
Function ngto(N:integer):Boolean;
Var i:integer;
Begin
ngto:=false;
For i:=2 to trunc(sqrt(N)) do
if N mod i = 0 then exit;
ngto:=true;
End;

- cách nì là tốt nhất ùi , thêm dk "if n<2 then exit"
- Hàm kt ng tố đã có topic thảo luận ùi , có các pro nhận xét đầy đủ lun , bld thử tìm xem

**elnino_020993** · 16-07-2009 15:41

còn có thể cải tiến được nữa đấy bạn ạh
vòng for làm cho i có thể là số chẵn,
mình đề nghị dùng vòng repeat .. until
chỉ phải ktra ban đầu với giá trị i=2;
sau đó i=3, qua mỗi vòng lặp thì inc(i,2);

**lehang_gb1** · 16-07-2009 15:54

Code:

Function nt(x:integer):boolean;
Var i:integer;
Begin
  nt:=true;
For i:=2 to trunc(sqrt(x)) do
  if x mod i =0 then
     nt:=false;
End;

[=========> Bổ sung bài viết <=========]

Được gửi bởi elnino_020993

còn có thể cải tiến được nữa đấy bạn ạh
vòng for làm cho i có thể là số chẵn,
mình đề nghị dùng vòng repeat .. until
chỉ phải ktra ban đầu với giá trị i=2;
sau đó i=3, qua mỗi vòng lặp thì inc(i,2);

Có thể qua mỗi vòng lặp tăng i lên 2 sẽ bớt thời gian thực hiện. Vì ko bao giờ có 2 số tự nhiên liên tiếp cùng là nguyên tố đúng ko bạn nhỉ

[=========> Bổ sung bài viết <=========]

Code:

Function nt(x:integer):boolean;
Var i:integer;
Begin
if (x=2) or (x=3) then nt:=true
else nt:=false;
i:=2
 repeat
    if x mod i then exit else inc(i,2);
 until i=trunc(sqrt(x));
nt:=N>1;
End;

[=========> Bổ sung bài viết <=========]

Cũng ko cần kiểm tra x=2 or x=3 vấn đúng.Kiẻm tra TH N=1;
Function nt(x:integer):boolean;

Code:

Var i:integer;
Begin
if x=1 then nt:=false;exit;

 nt:=false;
i:=2
 repeat
    if x mod i then exit else inc(i,2);
 until i=trunc(sqrt(x));
nt:=true;
End;

**quangtq** · 16-07-2009 18:44

Bạn lehang viết bằng TP à?
FP viết dễ hơn:

PHP Code:


Function NT(n:Cardinal):Boolean;
Var i:Cardinal;
Begin
     i:=2;
     If N<=1 then Exit(False)
     Else While i<=Trunc(Sqrt(N))do
       Begin
        If N mod i = 0 then Exit(False);
        i+=2;
       End;
     Exit(True);
End;