2 Lập trình và thực ganh đua bên trên PC một số trong những thuật toán số
2.2 Kiểm tra số nguyên vẹn tố
2.2.1 Lập trình bên trên lịch trình Pascal
Ý tưởng Số yếu tố là số phân chia cho một và chủ yếu nó. Giả sử số vừa vặn nhập vào là n, tớ mang đến i chạy kể từ 2 cho tới n−1, nếu như n phân chia không còn mang đến i vô bất cứ lần lặp này thì tức là n ko yếu tố, còn nếu như không phân chia không còn mang đến bất cứ lượt lặp này thì n là số yếu tố.
Bạn đang xem: viết chương trình kiểm tra số nguyên tố trong pascal
PROGRAM kiem tra ví nguyen to; USES crt;
VAR n,i,a:INTEGER; BEGIN
Clrscr;
Write(’nhap vao 1so:’); readln(n);
a:=0;
For i:=2 to tướng n do
if(n mod i=0)then a:=a+1;
if a< 2 then writeln(n,’ la ví nguyen to’) else writeln(n,’ khong la ví nguyen to’); Readln;
END.
Ví dụ 2.12 Kiểm tra coi số 3041975 liệu có phải là số yếu tố hoặc không Chạy lịch trình bên trên Pascal tớ đem sản phẩm như sau
Nhap vao 1so:3041975 Ket qua
Ví dụ 2.13 Viết lịch trình in đi ra toàn bộ những số yếu tố bé thêm hơn hoặc bằng n (giải thuật sàng Eratosthenes).
Mã chương trình
Program Chuong trinh tiết kiem tra chạm in ví nguyen to; uses crt; var n, i, j:longint; ok:boolean; Begin clrscr; write(’Nhap n: ’); readln(n);
write(‘cac ví nguyen to tướng nho hon ’, n, ’ la ’); for i:= 2 to tướng n do begin ok:=true; for j:= 2 to tướng i-1 do if i mod j =0 then ok:=false; if ok then write(i, ’; ’); end; readln; End.
Ví dụ 2.14 In đi ra toàn bộ những số yếu tố bé thêm hơn hoặc vì như thế 1000. Chạy lịch trình bên trên Pascal tớ được sản phẩm sau
Nhap n:1000
Cac ví nguyen to tướng nho hon 1000 la
2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149, 154; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 491; 499; 503; 509; 521; 523; 541; 547; 557; 563; 569; 571; 577; 587; 593; 599; 601; 607; 613; 617; 619; 631; 641; 643; 647; 653; 659; 661; 673; 677; 683; 691; 701; 709; 719; 727; 733; 739; 743; 751; 757; 761; 769; 773; 787; 797; 809; 811; 821; 823; 829; 839; 853; 857; 859; 863; 877; 881; 883; 887; 907; 911; 919; 929; 937; 941; 947; 953; 967; 971; 977; 983; 991; 997.
2.2.2 Tính toán bên trên Maple
Muốn đánh giá một số trong những liệu có phải là số yếu tố hay là không tớ sử dụng lệnh
[> isprime(a);
Ví dụ 2.15 Kiểm tra coi 210219871988 và 21283 đem là số yếu tố hay không.
[> isprime(210219871988);
false [> isprime(21283);
Kiểm tra số Carmichael
Ta triển khai công việc bám theo ví dụ sau. Ví dụ 2.16 (Bài 27, [2])
Chứng minh rằng 294409 là một số trong những Carmichael. Giải
Trước không còn tớ nhập vô số nguyên vẹn dương n cần thiết kiểm tra
[> n:=294409;
n:=294409 Kiểm tra coi n đem là số yếu tố hoặc không?
[> isprime(n);
False
Nếu n là số yếu tố thì nó ko cần là số Carmichael. trái lại, ta tiếp tục phân tách n kết quả những quá số nguyên vẹn tố
[> L:=ifactor(n);
L:=(37)(73)(109)
Nếu mang trong mình một quá số đem số nón to hơn 1 thì Tóm lại n ko cần là số Carmichael, ngược lại tớ kế tiếp đánh giá. Trước tiên tớ lập danh sách các quá số yếu tố (có vô phân tách nêu trên) q = [q1, q2, ...qk] bằng lệnh sau:
[> q:=[37,73,109];
q:=[37,73,109]
Xem thêm: vở bài tập toán lớp 5 tập 2 trang 69, 70
Sau cơ tổ chức đánh giá tính phân chia không còn của những quy tắc phân chia số n−1 cho các số (qi−1), i = 1,2, ...k. Việc này cũng tương tự với việc coi các thành phần vô list những phần dư đem vì như thế 0 hay là không vì như thế lệnh
[> [seq(irem(n-1,q[i]-1),i=1..nops(q))]; [0,0,0]
Nếu vô list cơ đem bộ phận không giống 0 thì n ko cần số Carmichael, ngược lại mang đến sản phẩm là số Carmichael.
Kết ngược đã cho thấy số 294409 là số Carmichael. Kiểm tra số fake nguyên vẹn tố
Muốn đánh giá n đem cần số fake yếu tố hạ tầng a hay là không tớ chỉ cần chỉ đi ra rằng n ko cần là số yếu tố tiếp sau đó đánh giá điều kiện
(an−a) modn = 0,
có được vừa lòng hay là không. Các bước được triển khai qua loa ví dụ sau. Ví dụ 2.17 Kiểm tra coi số 56348327841 đem là số fake yếu tố hạ tầng 2 hay không?
Nhập vô nhì số nguyên vẹn a, n vì như thế những lệnh
[> n:=56348327841; a:=2;
n:=56348327841 a:=2 Kiểm tra coi n đem là số yếu tố hoặc không
[> isprime(n);
false
Nếu n là số yếu tố thì nó ko cần là số fake yếu tố. trái lại, ta tiến hành đánh giá ĐK (an−a) modn = 0 đã có được vừa lòng hay không vì như thế lệnh
[> is(a&∧n −a mod n = 0);
false
Nếu sản phẩm là true thì n thực sự số fake yếu tố hạ tầng a ngược lại thì không cần. Kết ngược đã cho thấy số 56348327841 ko cần là số fake nguyên tố hạ tầng 2.
Ví dụ 2.18 Kiểm tra coi số 1373653 đem là số fake yếu tố hạ tầng 3 hay không? [> n:=1373653; a:=3; n:=1373653 a:=3 [> isprime(n); false [> is(a&∧n−a mod n = 0);
true
Kết ngược đã cho thấy số 1373653 là số fake yếu tố hạ tầng 3. Kiểm tra số fake yếu tố mạnh
Muốn đánh giá số nguyên vẹn dương lẻ n đem cần số fake yếu tố mạnh cơ
sở a hay là không tớ chỉ việc cho rằng n ko cần là số yếu tố sau
đó đánh giá coi nó đem trải qua loa được đánh giá Miller hay là không. Qui trình
kiểm tra Miller được triển khai qua loa công việc sau.
Bước 1. Phân tích n−1 đi ra quá số nguyên vẹn tố
[> ifactor(n−1);
Bước 2. Từ sản phẩm phân tách bên trên tớ biết n − 1 rất có thể ghi chép bên dưới dạng
n−1 = 2st (trong cơ s là số bất ngờ bất kì còn t là một số trong những lẻ), tớ kiểm tra coi ĐK tại đây đem vừa lòng hoặc không
[> is(a&∧t mod n= 1);
Nếu sản phẩm là true thì n là số fake yếu tố mạnh hạ tầng a, ngược lại thì ta đánh giá ĐK a2jt+ 1 mod n = 0 đã có được vừa lòng với 1 j nào đó trong vòng kể từ 0 cho tới s−1 hay là không. Nếu tồn bên trên j thì kết luận
n là số fake yếu tố mạnh hạ tầng a, ngược lại tớ Tóm lại là ko cần. Có thể triển khai điều này vì như thế mệnh lệnh sau
[> seq(a&∧((2∧j)∗t) + 1 mod n, j = 0..s−1);
Kết ngược của mệnh lệnh là một trong sản phẩm bao hàm s số bất ngờ, nếu như đem một số trong những trong dãy cơ vì như thế 0 thì Tóm lại n là số fake yếu tố mạnh hạ tầng a ngược lại ta Tóm lại là ko cần.
Ví dụ 2.19 Kiểm tra coi số 2532601 đem cần số fake yếu tố mạnh cơ sở 3 hoặc không? [> n:=25326001; a:=3; n:=25326001 a:=3 [> isprime(n); false [> ifactor(n−1); (2)4(3)3(5)3(7)(67) Ta có [> s:=4; t := 3∧3∗5∧3∗7∗67; s:=4 t:=1582875
[> is(a&∧t mod n= 1);
false
Ta đánh giá tiếp
[> seq(a&∧((2∧j)∗t) + 1 mod n, j = 0..s−1); 0,2,2,2
Một số ví dụ áp dụng
Bài 1 Chứng minh những số sau đấy là số Carmichael:
1729, 294409, 56052391, 118901521, 172947529. Bài 2 (Bài 28 [5])
Xem thêm: một số bài toán về đại lượng tỉ lệ thuận
Chứng minh rằng 6601 là một số trong những Carmichael.
Bài 3 Chứng minh rằng 1373653 là số fake yếu tố hạ tầng 2, 3 nhưng không là số fake yếu tố hạ tầng 5,7.
Bài 4 Chứng minh rằng 25326001 là số fake yếu tố mạnh hạ tầng 2, 3,5 nhưng ko là số fake yếu tố mạnh hạ tầng 7.
Bình luận