2 trang 128 lượt tải

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ơ

256

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: Trường Đại học Nam Cần Thơ 122 tài liệu

Tác giả:

Profile

Mai Nguyệt

1 năm trước
Tải xuống Chia sẻ Báo cáo
Danh sách Quiz
Tải xuống
/2
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;

Tài liệu khác của Trường Đại học Nam Cần Thơ

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;

Tài liệu liên quan: