# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Số nguyên tố!

## bonbonmedia

Các bạn chắc hẳn ai ai cũng biết đến *số nguyên tố*, việc xác định một số có phải là số nguyên tố hay không có thể dễ nhưng sẽ chạy khá lâu với dữ liệu vào. Vậy các bạn hãy cùng nhau đóng góp thuật toán của mình để tìm ra cách kiểm tra tính nguyên tố của một số được nhanh hơn nhé! :book:

----------


## phamhoasp

Như bạn đã bit là số nguyên tố là số chỉ chia hết cho 1 và cho chính nó, vậy thuật toán cổ xưa là phải xét từ 2 đến n-1 xem số n này có chia hết cho số nào không.

Vấn đề đặt ra là khi tồn tại ít nhất một số mà số n này chia hết trong dãy số từ 2->n-1 thì ta kết luận là số n này không phải là số nguyên tố, ngược lại tất nhiên là số nguyên tố rồi.

Nhưng với thuật toán như trên, ta phải tốn khá nhiều phép so sánh. Một điều khá hay mà ít ai nhận ra là một số nguyên không thể nào chia hết cho số nào nằm trong khoảng (n/2)+1 đến n-1.

Với điều thú vị như trên khi ta khảo sát một số có phải là một số nguyên tố hay không ta chỉ cần xét từ giá trị 2->(n/2) là được, thuật toán vẫn như trên ta tiết kiệm được 1/2 khoảng thời gian.

----------


## luxuryhanoi

> Như bạn đã bit là số nguyên tố là số chỉ chia hết cho 1 và cho chính nó, vậy thuật toán cổ xưa là phải xét từ 2 đến n-1 xem số n này có chia hết cho số nào không.
> 
> Vấn đề đặt ra là khi tồn tại ít nhất một số mà số n này chia hết trong dãy số từ 2->n-1 thì ta kết luận là số n này không phải là số nguyên tố, ngược lại tất nhiên là số nguyên tố rồi.
> 
> Nhưng với thuật toán như trên, ta phải tốn khá nhiều phép so sánh. Một điều khá hay mà ít ai nhận ra là một số nguyên không thể nào chia hết cho số nào nằm trong khoảng (n/2)+1 đến n-1.
> 
> Với điều thú vị như trên khi ta khảo sát một số có phải là một số nguyên tố hay không ta chỉ cần xét từ giá trị 2->(n/2) là được, thuật toán vẫn như trên ta tiết kiệm được 1/2 khoảng thời gian.


này bạn,
bạn có lộn ko vậy
(n/2) hay căn bậc 2 của n ???
theo tôi thì phải từ 2 đến trunc(sqrt(n)) mới đúng chứ nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG])

----------


## yentatoo

Mình xin nói một số vấn đề như sau:
- Thứ nhất, phần reply của bạn *taptanhtinhoc* đã có ở một forum khác mình tìm trên google cách đây khoảng nửa tháng, hoàn toàn nguyên văn với phần reply của bạn. Mong bạn nên ghi rõ nguồn gốc của một bài khi post lên nếu đó không thuộc sở hữu của bạn.
- Thứ hai, một trong những phương pháp kiểm tra số nguyên tố chỉ cần chạy đến phần nguyên căn bậc hai là đủ: trunc(sqrt(n)). Nhưng liệu có *tồn tại* một phương pháp nào đó nhanh hơn chăng?
*Thân.*

----------


## AllisOne-05

> Mình xin nói một số vấn đề như sau:
> - Thứ nhất, phần reply của bạn *taptanhtinhoc* đã có ở một forum khác mình tìm trên google cách đây khoảng nửa tháng, hoàn toàn nguyên văn với phần reply của bạn. Mong bạn nên ghi rõ nguồn gốc của một bài khi post lên nếu đó không thuộc sở hữu của bạn.


- Người ta lấy đâu kệ người ta . Người ta bik thì share . Thế thôi . Kiến thức đâu phải tự có : từ sách vở , từ thầy cô , từ GOOGLE . Chẳng nhẽ mỗi lần post kiến thức trong sách là phải vik rõ tên sách + tg , mỗi lần post kiến thức thầy cô truyền đạt phải chú thích "lời thầy cô " !? C thấy chẳng cần thiết & e cũng k nên bắt bẻ như thế . Mà còn chưa kể trường hợp , ng post ở 4rum kia là ban taptanhtinhoc thì sao

- Bài toán này thì thuộc dạng kinh điển và quá quen thuộc r` . Bàn hoài thì nhàm lắm . C sd cách for i:=2 to trunc(sqrt(n)) do ... và nghĩ rằng nó là tối ưu nhất trong HẦU HẾT CÁC TH


@ taptanhtinhoc : tên thật của bạn làm mình nhớ tới 1 ng =)) . THÚ VỊ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]) . Tốt nhất bạn k phải là ng đó

----------


## showbiz

Dưới đây là cách làm của mình, mình chỉ nghĩ ra nhanh đến thế thôi, bạn nào nghĩ ra cách nhanh hơn nữa không nhỉ:



```
[/FONT]
uses crt;
var n:longint;
function kt(n:longint):boolean;
var i:longint;
begin
     if n<2 then kt:=false
        else if n<4 then kt:=true
             else if ((n mod 6<>1) and (n mod 6<>5)) or (n mod 2=0) then kt:=false
                  else
                      begin
                           i:=3;
                           while i<=trunc(sqrt(n)) do
                                 if n mod i=0 then
                                    begin
                                         kt:=false;
                                         exit;
                                    end
                                    else inc(i,2);
                           kt:=true;
                      end;
end;
BEGIN
     readln(n);
     if kt(n) then write(‘snt’)
        else write(‘ko phai snt’);
     readln;
END.
```

*Thân.*

----------


## BRASOL

trong trường hợp tồi nhất : số n là snt thì bạn cũng ktra từ 3 đến trunc(sqrt(n)), chỉ có điều bạn tăng mỗi lần 2 đơn vị , bỏ qua số lẻ thôi.
Dù sao cũng thanks bạn

----------


## hoaican

> trong trường hợp tồi nhất : số n là snt thì bạn cũng ktra từ 3 đến trunc(sqrt(n)), chỉ có điều bạn tăng mỗi lần 2 đơn vị , bỏ qua số lẻ thôi.
> Dù sao cũng thanks bạn


 Bạn ơi, mình bỏ qua cả những số chia 6 không dư 1 hoặc 2 nữa đấy.
Ví dụ: gặp n=14,8,9,21,22 ... loại ngay :book:

----------


## tuylasg

Cách của anh binhnguyen dựa vào 1 tính chất ít biết đến của 1 số nguyên tố. Cách này mình cũng biết vì đọc được trong 1 cuốn sách. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Nếu thế thì có cần ghi tên tài liệu tham khảo không anh? [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Cách này là cách nhanh nhất roài. Ai có cách khác nhanh hơn mình thanks luôn.[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

----------


## thuyduong

> Cách của anh binhnguyen dựa vào 1 tính chất ít biết đến của 1 số nguyên tố. Cách này mình cũng biết vì đọc được trong 1 cuốn sách. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Nếu thế thì có cần ghi tên tài liệu tham khảo không anh? [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
> Cách này là cách nhanh nhất roài. Ai có cách khác nhanh hơn mình thanks luôn.[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]


 Nguồn tài liệu thì không có, vì đây là tính chất mình được học trên trường cấp 2. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Còn về phương pháp nhanh hơn thì mình chịu.
Chị hằng biết số nguyên tố ứng dụng nhiều thế nào không??? Trong cả *bài toán n (>=4) quân hậu* nữa đấy. :book:

----------


## hongkhanh

> Ơ. Bài quân hậu hình như dùng đệ quy mà, anh binhnguyen nói rõ hơn dùng snt vào bài quân hậu như nào đi.


 Nếu số quân hậu (n) là số nguyên tố thì ta có nghiệm đặt quân hậu là đường thẳng y=ax+b (a>1) trên mặt phẳng hữu hạn N x N (trong đó b điều chỉnh từ 0). _Phần này mình không rành lắm, mình còn đang nghiên cứu về hệ số a, b sao cho đến khi nào thì dừng._
Ví dụ:
- n=7.
- Bạn hãy đặt theo đường thẳng y=2x, y=3x, y=2x+1, y=3x+1 .v..vv...
*Sau khi mình nghiên cứu hoàn chỉnh từ các tập tư liệu mình sẽ post lên đầy đủ.*
*Thân.*

----------


## anhlinh123

> Bài những quân hậu mình ko biết ứng dụng snt như nào. Ai chỉ giùm mình. Bài đó là đệ quy chính hiệu mà.


Đệ quy quay lui thì với nghiệm thứ nhất bạn phải chạy bao nhiêu lần? 117 thì phải, tuy không tệ nhưng không phải là "nhanh".
Mình ví dụ nhé, khi nào mình nghiên cứu chuẩn thì mới post tất cả lên:
- 8 quân hậu: 2,4,6,8,3,1,7,5. Ta đặt quân hậu:
+ Theo thứ tự số từ trái qua phải là số dòng.
+ Giá trị số là số cột ở dòng đó.
+ Tọa độ: (1,2);(2,4);(3,6);(4,8);(5,3);(6,1);(7,7);(8,5).
- 5 (snt): 2,4,6,1,3,5.
.v..vv...
*Mình sẽ nói chi tiết vào topic khác*

----------


## quynhvunb

Thuật toán kiểm tra 1 số nguyên tố nhanh nhất mà mình biết là http://vi.wikipedia.org/wiki/Kiểm_tra_Miller-Rabin

----------


## chimoiminhem

Bổ sung, nâng cấp thuật toán:


```
function kt(n:longint):boolean;
var i,j:byte;
begin 
         kt:=true;
         if n<2 then begin kt:=false;exit; end;
         if n<4 then exit;
         if (n mod 6<>1) and (n mod 6<>5) then begin kt:=false;exit; end;
         if n<25 then exit;
         i:=5;j:=2;
         repeat
                  if n mod i=0 then 
                        begin
                                 kt:=false;
                                 exit;
                        end;
                  i:=i+j;
                  j:=6-j;
         until i>trunc(sqrt(n));
end;
```

Thuật toán đã nâng cấp khá nhanh so với thuật toán cũ mình đã post.

----------


## TruongTamPhong

*Hàm kiểm tra tính nguyên tố*

Tôi sưu tầm được cái này, gửi các bạn tham khảo (Free Pascal code):
*function* is_prime(n:longint):boolean;
*var* k,sqrt_n: longint;
*begin*
*if* (n=2)or(n=3) *then* exit(true);
* if* (n=1)or(n mod 2=0)or(n mod 3 =0) *then* exit(false);
sqrt_n := trunc(sqrt(n));
k:=-1;
* repeat*
inc(k,6);
if (n mod k = 0) or (n mod (k+2) =0) then break;
* until* k>sqrt_n;
exit(k>sqrt_n);
*end;*
Trên thực tế người ta hay dùng các thuật toán xác suất, các bạn có thể tìm đọc trên wikipedia

----------


## damynghebaoan

> Tôi sưu tầm được cái này, gửi các bạn tham khảo (Free Pascal code):
> *function* is_prime(n:longint):boolean;
> *var* k,sqrt_n: longint;
> *begin*
> *if* (n=2)or(n=3) *then* exit(true);
> *if* (n=1)or(n mod 2=0)or(n mod 3 =0) *then* exit(false);
> sqrt_n := trunc(sqrt(n));
> k:=-1;
> *repeat*
> ...


 Thuật toán giống của mình.
Mình chỉ sử dụng gộp lại thôi, nếu để ra trường hợp riêng thì là code của bạn.
Mình chỉ biết chứ chưa thấy thuật toán xác suất trong kiểm tra số nguyên tố.

----------

