viết chương trình kiểm tra số nguyên tố trong pascal

2 Lập trình và thực đua bên trên PC một trong những thuật toán số

2.2 Kiểm tra số vẹn toàn tố

2.2.1 Lập trình bên trên công tác Pascal

Ý tưởng Số yếu tắc là số phân tách cho một và chủ yếu nó. Giả sử số một vừa hai phải nhập vào là n, tớ mang lại i chạy kể từ 2 cho tới n−1, nếu như n phân tách không còn mang lại i nhập bất cứ lần lặp này thì Tức là n ko yếu tắc, còn nếu như không phân tách không còn mang lại bất cứ lượt lặp này thì n là số yếu tắc.

Bạn đang xem: viết chương trình kiểm tra số nguyên tố trong pascal

PROGRAM kiem tra so sánh nguyen to; USES crt;

VAR n,i,a:INTEGER; BEGIN

Clrscr;

Write(’nhap vao 1so:’); readln(n);

a:=0;

For i:=2 to lớn n do

if(n mod i=0)then a:=a+1;

if a< 2 then writeln(n,’ la so sánh nguyen to’) else writeln(n,’ khong la so sánh nguyen to’); Readln;

END.

Ví dụ 2.12 Kiểm tra coi số 3041975 liệu có phải là số yếu tắc hoặc không Chạy công tác bên trên Pascal tớ sở hữu thành quả như sau

Nhap vao 1so:3041975 Ket qua

Ví dụ 2.13 Viết công tác in rời khỏi toàn bộ những số yếu tắc 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 va vấp in so sánh nguyen to; uses crt; var n, i, j:longint; ok:boolean; Begin clrscr; write(’Nhap n: ’); readln(n);

write(‘cac so sánh nguyen to lớn nho hon ’, n, ’ la ’); for i:= 2 to lớn n do begin ok:=true; for j:= 2 to lớn i-1 do if i mod j =0 then ok:=false; if ok then write(i, ’; ’); end; readln; End.

Ví dụ 2.14 In rời khỏi toàn bộ những số yếu tắc bé thêm hơn hoặc vì thế 1000. Chạy công tác bên trên Pascal tớ được thành quả sau

Nhap n:1000

Cac so sánh nguyen to lớn 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 trong những liệu có phải là số yếu tắc hay là không tớ người sử dụng lệnh

[> isprime(a);

Ví dụ 2.15 Kiểm tra coi 210219871988 và 21283 sở hữu là số yếu tắc hay không.

[> isprime(210219871988);

false [> isprime(21283);

Kiểm tra số Carmichael

Ta tiến hành công việc theo dõi ví dụ sau. Ví dụ 2.16 (Bài 27, [2])

Chứng minh rằng 294409 là một trong những Carmichael. Giải

Trước không còn tớ nhập nhập số vẹn toàn dương n cần thiết kiểm tra

[> n:=294409;

n:=294409 Kiểm tra coi n sở hữu là số yếu tắc hoặc không?

[> isprime(n);

False

Nếu n là số yếu tắc thì nó ko nê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ố vẹn toàn tố

[> L:=ifactor(n);

L:=(37)(73)(109)

Nếu sở hữu một quá số sở hữu số nón to hơn 1 thì Tóm lại n ko nê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 (có nhập phân tách nêu trên) q = [q₁, q₂, ...q_k] bằng lệnh sau:

[> q:=[37,73,109];

q:=[37,73,109]

Xem thêm: tập làm văn lớp 3 kể về người hàng xóm

Sau cơ tổ chức đánh giá tính phân tách không còn của những quy tắc phân tách số n−1 cho các số (q_i−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 nhập list những phần dư sở hữu vì thế 0 hay là không vì thế lệnh

[> [seq(irem(n-1,q[i]-1),i=1..nops(q))]; [0,0,0]

Nếu nhập list cơ sở hữu bộ phận không giống 0 thì n ko nên số Carmichael, ngược lại mang lại thành quả là số Carmichael.

Kết trái khoáy đã cho chúng ta thấy số 294409 là số Carmichael. Kiểm tra số fake vẹn toàn tố

Muốn đánh giá n sở hữu nên số fake yếu tắc hạ tầng a hay là không tớ chỉ cần chỉ rời khỏi rằng n ko nên là số yếu tắc tiếp sau đó đánh giá điều kiện

(aⁿ−a) modn = 0,

có được vừa lòng hay là không. Các bước được tiến hành qua quýt ví dụ sau. Ví dụ 2.17 Kiểm tra coi số 56348327841 sở hữu là số fake yếu tắc hạ tầng 2 hay không?

Nhập nhập nhị số vẹn toàn a, n vì thế những lệnh

[> n:=56348327841; a:=2;

n:=56348327841 a:=2 Kiểm tra coi n sở hữu là số yếu tắc hoặc không

[> isprime(n);

false

Nếu n là số yếu tắc thì nó ko nên là số fake yếu tắc. trái lại, ta tiến hành đánh giá ĐK (aⁿ−a) modn = 0 đã đạt được vừa lòng hay không vì thế lệnh

[> is(a&^∧n −a mod n = 0);

false

Nếu thành quả là true thì n thực sự số fake yếu tắc hạ tầng a ngược lại thì không nên. Kết trái khoáy đã cho chúng ta thấy số 56348327841 ko nên là số fake nguyên tố hạ tầng 2.

Ví dụ 2.18 Kiểm tra coi số 1373653 sở hữu là số fake yếu tắc 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 trái khoáy đã cho chúng ta thấy số 1373653 là số fake yếu tắc hạ tầng 3. Kiểm tra số fake yếu tắc mạnh

Muốn đánh giá số vẹn toàn dương lẻ n sở hữu nên số fake yếu tắc mạnh cơ sở a hay là không tớ chỉ việc cho là n ko nên là số yếu tắc sau đó đánh giá coi nó sở hữu trải qua quýt được đánh giá Miller hay là không. Qui trình kiểm tra Miller được tiến hành qua quýt công việc sau.

Bước 1. Phân tích n−1 rời khỏi quá số vẹn toàn tố

[> ifactor(n−1);

Bước 2. Từ thành quả phân tách bên trên tớ biết n − 1 rất có thể viết lách bên dưới dạng

n−1 = 2^st (trong cơ s là số đương nhiên bất kì còn t là một trong những lẻ), tớ kiểm tra coi ĐK tại đây sở hữu vừa lòng hoặc không

[> is(a&^∧t mod n= 1);

Nếu thành quả là true thì n là số fake yếu tắc mạnh hạ tầng a, ngược lại thì ta đánh giá ĐK a^2jt+ 1 mod n = 0 đã đạt được vừa lòng với cùng 1 j nào đó trong tầm 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ắc mạnh hạ tầng a, ngược lại tớ Tóm lại là ko nên. Có thể tiến hành điều này vì thế mệnh lệnh sau

[> seq(a&^∧((2^∧j)∗t) + 1 mod n, j = 0..s−1);

Kết trái khoáy của mệnh lệnh là một trong những sản phẩm bao hàm s số đương nhiên, nếu như sở hữu một trong những trong dãy cơ vì thế 0 thì Tóm lại n là số fake yếu tắc mạnh hạ tầng a ngược lại ta Tóm lại là ko nên.

Ví dụ 2.19 Kiểm tra coi số 2532601 sở hữu nên số fake yếu tắc mạnh cơ sở 3 hoặc không? [> n:=25326001; a:=3; n:=25326001 a:=3 [> isprime(n); false [> ifactor(n−1); (2)⁴(3)³(5)³(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 đó là số Carmichael:

1729, 294409, 56052391, 118901521, 172947529. Bài 2 (Bài 28 [5])

Xem thêm: tìm gtln gtnn của hàm số lớp 12 nâng cao

Chứng minh rằng 6601 là một trong những Carmichael.

Bài 3 Chứng minh rằng 1373653 là số fake yếu tắc hạ tầng 2, 3 nhưng không là số fake yếu tắc hạ tầng 5,7.

Bài 4 Chứng minh rằng 25326001 là số fake yếu tắc mạnh hạ tầng 2, 3,5 nhưng ko là số fake yếu tắc mạnh hạ tầng 7.