Kiểm tra tính nguyên tố của 1 số

[seosgnl001]

Trong topic này mọi người cùng bàn luận về cách kiểm tra tính nguyên tố của 1 số sao cho nhanh nhất nhé, bộ nhớ có thể không cần tiết kiệm, quan trọng là tốc độ chạy chương trình (sao cho nếu tìm các số nguyên tố trong phạm vi 2->1 tỉ không toát mồ hôi là được). Lí do mình lập topic này là vì trong box có 1 bài tập về số nguyên tố nhưng vì chưa tối ưu được thuật toán kiểm tra tính nguyên tố nên mình chưa có code tối ưu [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](

[blackhat.teamseo]

Theo mình là Miller Rabin
http://vi.wikipedia.org/wiki/Ki%E1%BB%83m_tra_Miller-Rabin

Var    n:qword; 
        i:longint; 

        FUNCTION ngto(n:qword):boolean; 
        var    m,b,s:qword; i:longint; 
        begin 
                ngto:=true;m:=n-1;s:=0;b:=1; 
                While m mod 2=0 do 
                begin 
                        inc(s); 
                        m:=m div 2; 
                end; 
 
                for i:=1 to m do b:=(b*2)mod n; 
                If b=1 then exit 
                else 
                For i:=0 to s-1 do 
                begin 
                        If (b mod n)=n-1 then exit 
                        else b:=sqr(b)mod n; 
                end; 
                ngto:=false; 
        end; 

BEGIN
                readln(n); 
                for i:=3 to n do 
                begin 
                If i mod 2<>0 then 
                begin 
                if ngto(i) then writeln(i,' '); 
                end;  end; 
                readln; 
END.

p/s: ngưỡng mộ bạn Long thật, mình bỏ tin r` [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[ngoc_loanhn]

Chỗ tieulong là học WORD với EXCEL [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](
Topic này lập để bàn cách kiểm tra số nguyên tố nhé, các bài viết không phục vụ mục đích chính sẽ del sau 2->3 ngày!!

[tuananh22794]

Có 2 định lí sau hỗ trợ cực kì tốt cho việc kiểm tra tính nguyên tố:
_ Nếu n là một số nguyên tố lớn hơn 5 thì số dư của n cho 6 phải là 1 hoặc 5.
Định lý này cho phép chúng ta tìm các số nguyên tố theo bước tăng không phải là đơn vị mà là 2, 4, 2, 4...
_ Một số nguyên dương n là số nguyên tố nếu nó không chia hết cho bất kỳ số nào trong dãy các số nguyên tố nhỏ hơn hoặc bằng sqrt(n)

[Hongthanhauto]

Không biết liệu phương pháp này nhanh hơn không nhỉ ? (đã post rồi, mình copy lại)

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.

[chucvn]

Cách của binhnguyen nhanh hơn cách cơ bản là thử i=1 -> trunc(sqrt(n)). Nhưng mới chỉ áp dụng định lí đầu tiên mình đưa ra, nếu áp dụng đồng thời 2 định lí thì tốc độ sẽ nhanh hơn nhiều, bước tăng không phải chỉ là 2 mà là khoảng cách giữa 2 số nguyên tố liên tiếp với nhau.

[sondongho83]

Mọi người bàn luận sôi nổi ghê!Giải hộ em bài này với:
BT:Ta định nghĩa số ngtố là số có t/c sau:
+Là số lớn hơn 1 và chia hết cho 1 và chính nó.
Viết chương trình tìm tất cả các số có t/c sau:
+)Là 1 số có n chữ số(n>1).
+)Là 1 số nguyên tố.
+)Khi đổi vị trí các chữ số của số đã cho,ta đc 1 số mới,số ấy phải là 1 số nguyên tố.
+)Tổng các chữ số của số đã cho cũng là 1 số nguyên tố.
HELP ME!THANK YOU!

[Nlseo01]

Mọi người bàn luận sôi nổi ghê!Giải hộ em bài này với:
BT:Ta định nghĩa số ngtố là số có t/c sau:
+Là số lớn hơn 1 và chia hết cho 1 và chính nó.
Viết chương trình tìm tất cả các số có t/c sau:
+)Là 1 số có n chữ số(n>1).
+)Là 1 số nguyên tố.
+)Khi đổi vị trí các chữ số của số đã cho,ta đc 1 số mới,số ấy phải là 1 số nguyên tố.
+)Tổng các chữ số của số đã cho cũng là 1 số nguyên tố.
HELP ME!THANK YOU!

Không nhớ là sao bạn post bài này mà mình lại chưa từng đọc qua :| Sr nha, giờ nếu bạn còn tham gia diễn đàn thì khi đọc bài viết này bạn cho mình cái giới hạn để tìm số có các tính chất thỏa mãn nhé, chứ không tìm hết thì là điều không thể.

[komoro92]

Dài dòng quá , cái này dễ nhứt lun. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Nguyên cái program mà có bi nhiu đây thui kaka

Program ktsnt;
Uses crt;
Var
n,i:Longint;
kt:Boolean;

Begin
Clrscr;
Readln(n); kt:=True;
For i:=2 to Trunc(sqrt(n)) do
If n mod i = 0 then
Begin
kt:=False;
Break;
End;
If kt then Writeln('So nguyen to')
Else Writeln('Ko la so nguyen to');
Readln;
End.

[quan4747]

Dài dòng quá , cái này dễ nhứt lun. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] Nguyên cái program mà có bi nhiu đây thui kaka

Program ktsnt;
Uses crt;
Var
n,i:Longint;
kt:Boolean;

Begin
Clrscr;
Readln(n); kt:=True;
For i:=2 to Trunc(sqrt(n)) do
If n mod i = 0 then
Begin
kt:=False;
Break;
End;
If kt then Writeln('So nguyen to')
Else Writeln('Ko la so nguyen to');
Readln;
End.

Xin lỗi bạn nhưng hình như bạn chưa hiểu ngụ ý của topic này. Topic này là để mọi người đưa ra các cách kiểm tra nguyên tố NHANH NHẤT chứ không phải bình thường nhất. Cách của bạn đưa ra là cách phổ thông rồi.