Một số câu hỏi dành cho HSG Tin học 8

BỒI DƯỠNG HỌC SINH GIỎI
Ngày 16/4/2014
3 tiết
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.
Program Nguyen_to;
Var n,i:integer;
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
Write(`Nhap n: `);Readln(n);
i:=n;
Repeat i:=i+1;
Until NT(i);
Write(`So nguyen to nho nhat lon hon `,n, `la: `,i);
Readln
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.

Program Phan_tich;
var n,i: integer;
Begin
Write(`Nhap so can phan tich: `);Readln(n);
i:=2;
Write(`Ket qua phan tich:`);
Write(n,`=`);
While n>1 do
Begin
if n mod i = 0 then Begin Write(i,`.`); n:= n div i End
else i:=i+1;
End;
Readln
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:
Program Phan_tich_nguyen_to_2;
Var n, Max, so, i:byte;
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(i,`.`); n:=n div i end else i:=i+1;
End;

Begin
Write(`Nhap so n: `);Readln(n);
Max:=0;
For i:= 1 to n do if PTNT(i)>=Max then Begin Max:=PTNT(i); So:=i End;
Write(`So `,So,` co nhieu uoc nhat,`,so,` = `);
PT(So);
Readln
End.



Program Tong_nguyen_to;
Var i,n:integer;
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
Write(`Nhap so n: `);Readln(n);
For i:=2 to n div 2 do if (NT(i) and NT(n-i)) then Writeln(n,` = `,i,` + `,n-i);
Readln
End.