Các thuật toán về số nguyên tố I,Số nguyên tố
1,Định nghĩa: số nguyên tố là số tự nhiên chỉ có 2 ước là số 1 và chính nó VD: 2,3,5,7,11,...
2,Thuật toán kiểm tra số nguyên tố
-Đếm các ước từ 1 đến N, nếu có đúng 2 ước thì kết luận: số nguyên tố
-Cải tiến:+ Chỉ cần đếm các ước trong đoạn[1..N/2]
+ Kiểm tra số ước trong đoạn[2..sqrt(N)] +Thuật toán tăng 6 Thuật toán tăng 6: Function SNT(N:int64):boolean; Var Q,K;int64; Begin
If (N=2) or (N=3) then exit(true);
If (N<2) or (N mod 2=0) or (N mod 3=0) then exit(false); Q:=trunc(sqrt(N)); K:=-1; Repeat K:=K+6;
If (N mod K=0) or (N mod(k+2)=0) then break; Until K>Q; Exit(K>Q); End; II,Sàng nguyên tố Procedure SangNT; Const Max=10000000; Var mang:array[1.Max] of byte; Begin
For i:=1 to Max do mang[i]:=0; Q:=trunc(sqrt(Max)); For i:=2 to Q do Begin j:=i*i; while j<=Max do Begin Mang[j]:=1; j:=j+i; End; End;
For i:=2 to Max do if mang[i]=0 then write(i,#32); End;