Chuyên đề về bồi dưỡng học sinh giỏi môn tin học

I. Số nguyên tố
Một số tự nhiên N (N>1) là số nguyên tố nếu N có đúng hai ước số là 1 và N (tức là không có ước số nào trong đoạn [2, N-1].
Tính chất: Nếu N không có ước nào trong đoạn [2, ] thì N cũng không có ước nào trong đoạn [ ,N-1] , suy ra N là số nguyên tố
Kiểm tra số nguyên tố: Ta chỉ cần kiểm tra xem N có ước trong đoạn [2, ] hay không
I. Số nguyên tố
If N<2 then writeln(n, ` khong la so nguyen to`)
Else
Begin
i:=2;
While (i<=sqrt(N)) and (N mod i<>0) do i:=i+1;
If i>sqrt(N) then Writeln(N, ` la so nguyen to`)
Else Writeln(N, ` khong la so nguyen to`);
End;
I. Số nguyên tố
Bài toán: Liệt kê các số nguyên tố trong đoạn [1,N]

Cách 1: Thử lần lượt các số M trong đoạn [1,N] rồi kiểm tra tính nguyên tố của M

For M:=2 to N do
Begin
i:=2;
While (i<=sqrt(M)) and (M mod i<>0) do i:=i+1;
If i>sqrt(M) then Writeln(M)
End;
I. Số nguyên tố
Cách 2: Sử dụng phương pháp sàng Eratosthene
Trước tiên xóa bỏ số 1 ra khỏi tập các số nguyên tố. Số tiếp theo số 1 là số 2 chính là số nguyên tố, xóa tất cả các bội của 2 ra khỏi bảng.
Số đầu tiên không bị xóa sau số 2 sẽ là số nguyên tố tiếp theo (số 3), xóa các bội của 3…
Quá trình tiếp tục đến khi gặp số nguyên tố lớn hơn sqrt(N) thì dừng. Tất cả các số chưa bị xóa là số nguyên tố.
I. Số nguyên tố
Cách 2: Sử dụng phương pháp sàng Eratosthene

Const max=100000;
Var P:Array[1..max] of byte;
i,j,N:Longint;
Begin
Write(`Nhap so tu nhien N =`);
Readln(N);
Fillchar(P,Sizeof(P),0);
For i:=2 to trunc(sqrt(N)) do
If P[i]=0 then
Begin
j:=i*i;
While j<=N do
Begin
P[j]:=1;
j:=j+i;
End;
End;
For i:=2 to N do
If P[i]=0 then Writeln(i);
End.

II. Ước số - Bội số
Ước số chung lớn nhất của hai số
Thuật toán Euclid:
a nếu b = 0
UCLN(a,b) =
UCLN(b, a mod b) nếu b<>0

While b>0 do
Begin
r := a mod b;
a := b;
b := r;
End;
II. Ước số - Bội số
Bội số chung nhỏ nhất của hai số
Áp dụng công thức:

UCLN(a,b) * BCNN(a,b) = a*b

 Tìm UCLN rồi áp dụng công thức trên suy ra BCNN
II. Ước số - Bội số
Bội số chung nhỏ nhất của hai số
Áp dụng công thức:

UCLN(a,b) * BCNN(a,b) = a*b

 Tìm UCLN rồi áp dụng công thức trên suy ra BCNN

* Chú ý: Hai số tự nhiên gọi là nguyên tố cùng nhau khi chúng có UCLN bằng 1
II. Ước số - Bội số
Một số dạng bài tập:
Đếm số các ước số
Tính tổng các ước số
Phân tích ra thành thừa số nguyên tố
…
III. Xử lý các chữ số
Bài toán:
Cho số tự nhiên N. Yêu cầu:
a) Đếm số chữ số của N
b) Tính tổng các chữ số của N
c) Tìm chữ số đầu tiên của N
d) Tìm số đảo ngược các chữ số của N
Hai phép toán cơ bản: DIV và MOD
a := N mod 10;
N := N div 10;
 lấy chữ số tận cùng của N
 Xóa bỏ chữ số tận cùng của N
III. Xử lý các chữ số
271958
27195
2719
271
27
2
0
8
5
9
1
7
2
0
1
2
3
4
5
6
0
8
13
22
23
30
32
859172
85917
8591
859
85
8
0
Dem:=0;
Tong:=0;
Dao:=0;
Repeat
a := N mod 10;
Dem := Dem + 1;
Tong:= Tong + a;
Dao := Dao * 10 + a
N:=N div 10;
Until N=0;
Writeln(`So chu so = ` , Dem);
Writeln(`Tong chu so = ` , Tong);
Writeln(`Chu so dau tien = ` , a);
Writeln(`So dao nguoc lai = ` , Dao);
III. Xử lý các chữ số
Một số bài toán tương tự:
- Xóa chữ số tận cùng bên trái của N
- Đổi chỗ chữ số đầu và chữ số cuối của N
- Xóa khỏi N tất cả các chữ số 0 và 5
- Tìm chữ số tận cùng của 2N
- …
IV. Một số bài toán khác
Số hạnh phúc là số có 2N chữ số sao cho tổng N chữ số đầu bằng tổng N chữ số cuối. Tìm các số hạnh phúc có 2N chữ số (1N4).
Số Palindrom là số mà khi viết các chữ số theo thứ tự ngược lại thì số tạo thành cũng chính bằng số ban đầu. Tìm các số Palindrom có K chữ số (1K9)
Số hoàn hảo là số có giá trị bằng tổng các ước số của nó (không kể ước số là chính nó). Tìm các số hoàn hảo trong đoạn [a,b] với 1ab108
Hai số gọi là đôi bạn nếu tổng các ước số của số này bằng số kia và ngược lại. Tìm các cặp số là đôi bạn trong đoạn [a,b]

IV. Một số bài toán khác
…