CHƯƠNG VII CHUYÊN ĐỀ CHIA HẾT – SỐ NGUYÊN TỐ

- :

.

- :

Nhập vào một số nguyên dương n. Hãy in ra số nguyên tố nhỏ nhất lớn hơn n.

- Thực hiện cho đến khi i là nguyên tố việc tăng i lên 1.

Nhập vào từ bàn phím số tự nhiên n (n<1000). Hãy phân tích n thành tích các thừa số nguyên tố.

Thuật toán:

Gán i := 2;

Khi n > 1 thì lặp:

Nếu n chia hết cho i thì in ra i và gán lại n:= n div i. Ngược lại tăng i lên 1.

var n,i: integer; f,g:text; Begin Assign(f,’Bai7_2.inp’);reset(f); Assign(g,’Bai7_2.out’);rewrite(g); Readln(f,n); i:=2; Write(g,'Ket qua phan tich:'); Write(g,n,'='); While n>1 do Begin if n mod i = 0 then Begin Write(g,i,'.'); n:= n div i End else i:=i+1; End; Close(f);close(g); End.

Nhận xét: Cài đặt trên in dư một dấu nhân ở cuối. Hãy chỉnh sửa để bỏ dấu nhân thừa này.

Bài tập 7.3:

Tìm các số tự nhiên nhỏ hơn hoặc bằng n mà sau khi làm phép phân tích ra thừa số nguyên tố có nhiều nhân tử nhất.

Thuật toán:

Cài đặt:

Var n, Max, so, i:byte; F,g:text; Function PTNT(n:integer):byte; Var i,p:byte; Begin i:=2; p:=0; While n>1 do if (n mod i)=0 then Begin p:=p+1; n:=n div i end else i:=i+1; PTNT:=p; End; Procedure PT(n:integer); Var i:byte; Begin i:=2; While n>1 do if (n mod i)=0 then Begin Write(g,i,'.'); n:=n div i end else i:=i+1; End; Begin Assign(f,’Bai7_3.inp’);reset(f); Assign(g,’Bai7_3.out’);rewrite(g) Readln(f,n); Max:=0; For i:= 1 to n do if PTNT(i)>=Max then Begin Max:=PTNT(i); So:=i End; Write(g,'So ',So,' co nhieu uoc nhat,',so,' = '); PT(So); Close(f);close(g); End.

Bài tập 7.4:

Viết chương trình cho phép phân tích một số ra thừa số nguyên tố và ghi kết quả dưới dạng tích các lũy thừa. Ví dụ: 300 = 2^2.3.5^2

Thuật toán:

Dùng một mảng để lưu lũy thừa. Mảng này có giá trị các phần tử ban đầu đều bằng 0. Nếu n chia hết cho i thì tăng M[i] lên 1.

Khi in kiểm tra: Nếu M[i] >0 thì in i^M[i].

Cài đặt:

Var M: array[1..1000] of byte; i: byte; n: integer; f,g:text; Begin For i:=1 to 1000 do M[i]:=0; Assign(f,’bai7_4.inp’);reset(f); Assign(g,’bai7_4.out’);rewrite(g); Readln(f,n); i:=2; While n>1 do if (n mod i = 0) then begin M[i]:=M[i]+1; n:=n div i End else i:=i+1; For i:=1 to 1000 do if M[i]>0 then Begin If M[i]>1 then Write(g,i,'^',M[i],'.') else Write(g,i,'.') End; Close(f);close(g); End.

Mọi số tự nhiên đều có thể viết được dưới dạng tổng của hai số nguyên tố. Viết chương trình thực hiện tách một số tự nhiên thành tổng của hai số nguyên tố.

Thuật toán:

Cài đặt:

Var i,n:integer; F,g:text; Function NT(n:integer):Boolean; Var ok: Boolean; i:integer; Begin ok:=true; For i:=2 to n-1 do if (n mod i) = 0 then ok:=ok and false; if n>=2 then NT:=ok else NT:=false; End; Begin Assign(f,’Bai7_5.inp’);reset(f); Assign(g,’Bai7_5.out’);rewrite(g); Readln(f,n); For i:=2 to n div 2 do if (NT(i) and NT(n-i)) then Writeln(g,n,' = ',i,' + ',n-i); Close(f);close(g); End.

Nhận xét: Hãy mở rộng bài toán theo hướng

- Xét xem trong đoạn [n1...n2] số nào cho phép tách thành tổng hai số nguyên tố nhiều trường hợp nhất.

- Tách một số thành tổng ba số nguyên tố.