Các thuật toán về số nguyên tố - Tin học (Tin học căn bản) | Trường Đại học Nam Cần Thơ
Các thuật toán về số nguyên tố - Tin học (Tin học căn bản) | Trường Đại học Nam Cần Thơ được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Tin học (Tin học căn bản) 12 tài liệu
Trường: Đại học Nam Cần Thơ 96 tài liệu
Tác giả:
Preview text:
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;