CHƯƠNG VII
CHUYÊN ĐỀ CHIA HẾT – SỐ NGUYÊN TỐ.
A. LÝ THUYẾT:
- :
- :
.
- :
B. BÀI TOÁN:
Bài tập 7.1 :
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.
VD: Nhập n = 10. Kết quả in ra số 11.
Giải thuật :
- Gán i := n ;
- Thực hiện cho đến khi i là nguyên tố việc tăng i lên 1.
Var n,i: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:=false else NT:=ok;
End;
Begin
Assign(f,’Bai7_1.inp’);reset(f);
Assign(g,Bai7_1.out’);rewrite(g);
Readln(f,n);
i:=n;
Repeat i:=i+1;
Until NT(i);
Write(g,'So nguyen to nho nhat lon hon ',n, 'la: ',i);
Close(f);close(g);
End.
|
Bài tập 7.2 :
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ố.
VD: Nhập vào n = 9 được 9 = 3.3
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.
Ví dụ n=9 . Các số có nhiều nhân tử nhất sau khi làm phép phân tích là: 8 = 2.2.2
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.
|
Bài tập 7.5
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ố.
Chia sẻ với bạn bè của bạn: |