Sáng kiến kinh nghiệm Vận dụng thuật toán về số nguyên tố để giải các bài toán

guyên dương 
N; 
Kết quả: Ghi ra filevăn bản PASS.OUT hai số nguyên K1 và K2. 
Ví dụ: 
PASS.INP PASS.OUT 
12 2 5 
Ràng buộc: 
 Có 30% số các test ứng với 30% số điểm của bài có 𝑁 ≤ 1000; 
 Có 40% số test khác ứng với 40% số điểm của bài có 𝑁 ≤ 104; 
 Có 30% số test còn lại ứng với 30% số điểm của bài có 𝑁 ≤ 106. 
Hướng dẫn: 
 Bài này yêu cầu chỉ đơn giản là xây dựng sàng lọc ra các số nguyên tố nhỏ 
hơn hoặc bằng N. Đếm số lượng các số nguyên tố và tính tổng các số nguyên tố 
đó. 
26 
const fi = 'pass.inp'; 
 fo = 'pass.out'; 
var f,g : text; 
 p : array[0..1001] of boolean; 
procedure xuly; 
 var d, n,kk,j,k,i,s:longint; 
 Begin 
 fillchar(p,sizeof(p),true); k:=0;s:=0; 
 readln(f,n); 
 for i:=2 to n do 
 if n mod i =0 then 
 begin 
 if (p[i]) then 
 begin 
 inc(k); s:=s+i; 
 for j:=1 to (n div i) do p[j*i]:=false; 
 end; 
 end; 
 writeln(g,k,' ',s ) 
 end; 
Begin 
 assign(f,fi); assign(g,fo); 
 reset(f); rewrite(g); 
 Begin 
 xuly; 
 end; 
 close(g); 
end. 
Bài 3. Số gần hoàn hảo 
27 
 Một số nguyên dương N được gọi là số "gần hoàn hảo" nếu thỏa mãn 
điều kiện: 2* N ≤ A, với A là tổng các ước số của N. 
Chẳng hạn: 12 là một số "gần hoàn hảo" vì: 2*12 < 1+2+3+4+6+12. 
Yêu cầu: Với K số nguyên dương, hãy kiểm tra xem các số nguyên dương 
đó có phải là số "gần hoàn hảo" hay không? 
Dữ liệu vào: Từ tệp GHH.INP có cấu trúc như sau: 
- Dòng đầu tiên chứa số nguyên dương K (K ≤ 100). 
- Dòng thứ hai chứa K số nguyên dương A1, A2,, AK (Ai ≤ 109 với 1≤ i ≤ K). 
Dữ liệu ra: Ghi vào tệp GHH.OUT gồm K dòng, dòng thứ i ghi số 1 nếu Ai là 
số "gần hoàn hảo", ngược lại ghi số 0. 
Ví dụ: 
GHH.INP GHH.OUT 
3 
6 16 12 
1 
0 
1 
Ràng buộc: 
Subtask 1: Có 60% điểm tương ứng với trường hợp Ai ≤ 106 với 1≤ i ≤ K. 
Hướng dẫn: 
Ta phân tích các số nguyên dương N thành tích các thừa số nguyên tố, sau 
đó áp dụng công thức để tính tổng các ước của nó. 
 Để thuật toán nhanh hơn có thể áp dụng sàng số nguyên tố. 
Chương trình: 
const 
 fi='GHH.INP'; 
 fo='GHH.OUT'; 
 maxn=100000; 
Var A:array[1..maxn] of longint; 
 gt,gtmu:array[1..maxn] of longint; 
 K:longint; 
procedure docdl; 
var f:text; 
28 
 i:longint; 
Begin 
 assign(f,fi); 
 reset(f); 
 readln(f,k); 
 For i:=1 to k do read(f,a[i]); 
 close(f); 
end; 
Function lt(x,n:longint):int64; 
Var i:longint; 
 t:int64; 
Begin 
 t:=1; 
 For i:=1 to n do t:=t*x; 
 exit(t); 
end; 
Function tonguoc(x:longint):int64; 
Var y,i,k,sl:longint; 
 s:int64; 
Begin 
 y:=trunc(sqrt(x)); 
 sl:=0; 
 i:=2; 
 k:=0; 
 repeat 
 while x mod i 0 do begin inc(i); k:=0; end; 
 inc(k); 
 x:=x div i; 
 if x mod i0 then 
 Begin 
 inc(sl); 
29 
 gt[sl]:=i; 
 gtmu[sl]:=k; 
 end; 
 until (i>y) or (x=1); 
 if x1 then 
 Begin 
 inc(sl); 
 gt[sl]:=x; 
 gtmu[sl]:=1; 
 end; 
 s:=1; 
 For i:=1 to sl do 
 s:=s*((lt(gt[i],gtmu[i]+1)-1) div (gt[i]-1)); 
 exit(s); 
end; 
Function ghh(x:longint):boolean; 
Begin 
 if tonguoc(x)>=2*x then exit(true); 
 exit(false); 
end; 
Procedure ghikq; 
Var f:text; 
 i:longint; 
Begin 
 Assign(f,fo); 
 rewrite(f); 
 for i:=1 to k do 
 if ghh(a[i]) then writeln(f,1) 
 else writeln(f,0); 
 close(f); 
30 
end; 
BEGIN 
 Docdl; 
 ghikq; 
END. 
Bài 4. Số nguyên tố tốt nhất 
Nói số a tốt hơn b nếu tổng bình phương các chữ số của a (trong hệ cơ số 
10) lớn hơn tổng bình phương các chữ số của b hoặc các tổng này bằng nhau 
nhưng a < b. 
Yêu cầu: Cho hai số nguyên l và r (2 ≤ l ≤ r ≤ 50 000). Hãy tìm số nguyên 
tố tốt nhất trong khoảng [l, r]. Nếu trong khoảng này không có số nguyên tố nào 
thì đưa ra số -1. 
Input: 
Một dòng chứa hai số l, r 
Output: 
Kết quả tìm được 
Ví dụ: 
NTTOTNHAT.INP NTTOTNHAT.OUT 
2 28 19 
Thuật toán: 
- Tính tổng bình phương các chữ số của a, b 
- Dùng sàng nguyên tố để lọc ra các số lớn hơn hoặc bằng l và bé hơn hoặc 
bằng r. 
Chương trình: 
const 
 tfi='nttotnhat.inp'; 
 tfo='nttotnhat.out'; 
var m, n: longint; 
 NT: array[0..50001] of longint; 
procedure SangNT; 
var i,j: longint; 
31 
begin 
 NT[1]:=1; 
 i:=1; 
 repeat 
 repeat inc(i) until (i>trunc(sqrt(n))) or (nt[i]=0); 
 if i<=trunc(sqrt(n)) then 
 begin 
 j:=2; 
 while j*i<=n do 
 begin 
 nt[j*i]:=1; 
 inc(j); 
 end; 
 end; 
 until i>trunc(sqrt(n)); 
end; 
function TongBP(x: longint): longint; 
var s: string; 
 t, i: longint; 
begin 
 str(x,s); 
 t:=0; 
 for i:=1 to length(s) do t:=t+sqr(ord(s[i])-48); 
 exit(t); 
end; 
procedure main; 
var i,ds, max,t: longint; 
begin 
 assign(input,tfi); reset(input); 
 assign(output,tfo); rewrite(output); 
 read(m,n); 
32 
 sangNT; 
 max:=0; 
 ds:=-1; 
 for i:=m to n do if nt[i]=0 then 
 begin 
 t:=TongBP(i); 
 if (max=0) or (t>max) then 
 begin 
 max:=t; 
 ds:=i; 
 end; 
 end; 
 writeln(ds); 
 close(input); close(output); 
end; 
BEGIN 
 main; 
END. 
Bài 5. Vòng số nguyên tố 
Một vòng tròn chứa 2*n vòng tròn nhỏ. Các vòng tròn nhỏ được đánh số 
từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*n 
mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ 
liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1. 
Input 
Số nguyên dương n ( 1 < n < 10 ) . 
Output 
Dòng đầu tiên ghi ra số k là số cách tìm được. 
K dòng tiếp theo mỗi dòng ghi ra 1 cách điền các số vào các vòng tròn nhỏ. 
Cách điền nào có thứ tự từ điển nhỏ hơn thì xếp trước. Nếu K > 10000 thì chỉ 
cần ghi ra 10000 cách đầu tiên. 
Ví dụ 
33 
Input: 
4 
Output: 
4 
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2 
Thuậ toán: 
- Viết sẳn thủ tục sàng số nguyên tố 
- Áp dụng thuật toán quay lui để chọn các số, kiểm tra điều kiện dựa trên 
mảng sàng SNT. 
– Vì N<10 nên có thể tính trước kết quả K và bỏ vào mảng hằng chỉ việc 
xuất ra. Giúp tiết kiệm được bộ nhớ và thời gian khi quay lui. 
Chương trình: 
const fi=''; 
 fo=''; 
 nmax=10; 
type data=longint; 
var 
 f:text; 
 SNT:array[1..50] of boolean; 
 n:data; 
 DD:array[1..nmax*2] of boolean; 
 KQ:array[1..nmax*2] of byte; 
 sl:data; 
 LUUTRU:array[1..16000020] of byte; 
 spt,k:longint; 
procedure sangnt; 
var i,j:data; 
34 
begin 
 fillchar(snt,sizeof(snt),true); 
 i:=2; 
 snt[1]:=false; 
 while i<=sqrt(50) do 
 begin 
 while snt[i]=false do 
 inc(i); 
 for j:=2 to 50 div i do 
 snt[i*j]:=false; 
 inc(i); 
 end; 
end; 
 procedure init; 
begin 
 fillchar(dd,sizeof(dd),false); 
 dd[1]:=true; 
 sl:=1; 
 kq[1]:=1; 
 spt:=0; k:=0; 
end; 
 procedure xuli; 
var i:data; 
begin 
 if not snt[1+kq[sl]] then exit; 
 inc(k); 
 for i:=1 to sl do 
 begin 
 inc(spt); 
 LUUTRU[spt]:=kq[i]; 
35 
 end; 
end; 
 procedure try; 
var j:data; 
begin 
 if sl=2*n then 
 begin 
 xuli; 
 end 
 else 
 for j:=2 to 2*n do 
 if (not dd[j]) and (SNT[kq[sl]+j]) then 
 begin 
 dd[j]:=true; 
 inc(sl); 
 kq[sl]:=j; 
 try; 
 dd[j]:=false; 
 dec(sl); 
 end; 
end; 
 procedure xuat; 
var i,tam:data; 
begin 
 assign(f,fo); rewrite(f); 
 writeln(f,k); 
 if k>10000 then 
 tam:=10000*2*n 
 else 
36 
 tam:=k*2*n; 
 for i:=1 to tam do 
 begin 
 write(f,luutru[i],' '); 
 if i mod (2*n) = 0 then writeln(f); 
 end; 
 close(f); 
end; 
begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 close(f); 
 SANGNT; 
 init; 
 try; 
 xuat; 
end. 
Bài 6. Số chính phương 
Bờm rất thích các số chính phương, muốn tìm hiểu về nó, và biết rằng số 
chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên phân 
biệt. Chẳng hạn: 9 = 1  9; 144 = 2  3  4  6. Bờm hay ngẫm nghĩ về nó mọi 
lúc khi có thời gian rãnh. Hôm nay, giờ giải lao trên lớp, Bờm quay sang đố 
Tuấn, với số tự nhiên N cho trước thì số chính phương lớn nhất được biểu diễn 
bằng tích của một tập các số tự nhiên phân biệt từ 1 đến N là bao nhiêu? Tuấn 
suy nghĩ mãi mà chưa trả lời được câu đố và thời gian thì ít quá. 
Yêu cầu: Cho một số nguyên N, hãy giúp Tuấn đưa ra số chính phương lớn 
nhất là tích của một tập các số tự nhiên phân biệt từ 1 đến N. Số đó có thể rất 
lớn nên chỉ cần xuất ra phần dư khi chia số đó cho 1000000007. 
Dữ liệu: Từ file văn bản SOCP.INP có cấu trúc: 
Một dòng duy nhất chứa số nguyên dương N. (N ≤ 4.104) 
37 
Kết quả: Ghi vào file văn bản SOCP.OUT có cấu trúc: 
Một dòng duy nhất là kết quả bài toán sau khi đã mod 1000000007 
Ví dụ 
SOCP.INP SOCP.OUT 
5 4 
 Subtask 1 (2 điểm): Giả thiết N≤ 102 . 
 Subtask 2 (2 điểm): Giả thiết N≤ 103 . 
 Subtask 3 (2 điểm): Giả thiết N≤ 4.104 . 
Thuật toán: 
- Phân tích số N! thành tích các thừa số nguyên tố, ghi nhận số lượng mỗi 
số bằng cách dùng sàng nguyên tố. Giả sử các thừa số đó là P1, P2, , Pk với các 
số mũ tương ứng là a1, a2, , ak. 
- Nếu ai lẻ thì giảm ai một đơn vị với mọi i = 1, 2, , k 
- Số chính phương lớn nhất cần tìm là tích các thừa số nguyên tố của các 
các số nguyên tố có số mũ chẵn lớn hơn 0. Chú ý khi tính ta mod với 
1000000007 
Chương trình: 
const fi='SOCP.INP'; 
fo='SOCP.OUT'; 
max=10000000; K=1000000007; 
var p,a:array[1..max] of longint; 
 NT:array[1..max] of boolean; 
 m,n,d:longint; 
 kq:int64; 
 f:text; 
Procedure Doc; 
begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 close(f); 
end; 
38 
Procedure Sang; 
var i,j:longint; 
begin 
 for i:=1 to n do nt[i]:=true; 
 nt[1]:=false; d:=0; 
 for i:=2 to n do 
 if nt[i] then 
 begin 
 inc(d); 
 P[d]:=i; 
 for j:=2 to n div i do nt[i*j]:=false; 
 end; 
end; 
FUNCTION mu(a,x:longint):int64; 
var t:int64; 
begin 
 if x=1 then exit(a); 
 t:=mu(a, x div 2); 
 t:=(t*t) mod k; 
 if x mod 2 0 then t:=(t*a) mod k; 
 exit(t); 
end; 
procedure xuly; 
var s,tg,i:longint; 
begin 
 for i:=1 to d do 
 begin 
 tg:=p[i]; s:=0; 
 while tg<=n do 
 begin 
 s:=s+ n div tg; 
39 
 tg:=tg*p[i]; 
 end; 
 a[i]:=s; 
 end; 
 kq:=1; 
 for i:=1 to d do 
 begin 
 if odd(a[i]) then dec(a[i]); 
 if a[i]>0 then kq:=(kq*mu(p[i],a[i])) mod k; 
 end; 
end; 
procedure ghi; 
begin 
 assign(f,fo); rewrite(f); 
 writeln(f,kq); 
 close(f); 
end; 
begin 
 doc; 
 sang; 
 xuly; 
 ghi; 
end. 
40 
Dạng 3: Phân tích thành các số nguyên tố 
Bài 1. Phân tích 
Cho số tự nhiên 2  n  105. Hãy phân tích n! ra tích của các thừa số 
nguyên tố theo trật tự tăng dần. Thí dụ, 4! = 23.31. 
Dữ liệu vào từ tệp văn bản PHANTICH.INP chỉ có một dòng chứa số tự nhiên 
n. 
Kết quả ghi ra tệp văn bản PHANTICH.OUT gồm các dòng, mỗi dòng ghi 
một thừa số nguyên tố tiếp đến là số mũ tương ứng. Các số trên cùng dòng 
cách nhau qua dấu cách. 
PHANTICH.INP PHANTICH.OUT 
4 2 3 
3 1 
Chương trình: 
const fi='PHANTICH.INP'; 
 fo='PHANTICH.OUT'; 
var n, dem, k:longint; 
 p, x: array[1..100000] of int64; 
procedure readfile; 
var f:text; 
begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 close(f); 
end; 
function nt(n: longint):boolean; 
var i: integer; 
begin 
 if n=1 then exit(false); 
 if n<4 then exit(true); 
 for i:=2 to trunc(sqrt(n)) do 
 if n mod i=0 then exit(false); 
41 
 exit(true); 
end; 
function sk(n:longint; p: longint): longint; 
var tam:longint; 
begin 
 tam:=0; 
 while n>=p do 
 begin 
 inc(tam,n div p); 
 n:=n div p; 
 end; 
 sk:=tam; 
end; 
procedure xuly; 
var i, y: longint; 
begin 
 for i:=2 to n do 
 if nt(i) then 
 begin 
 inc(dem); 
 p[dem]:=i; 
 x[dem]:=sk(n,i); 
 end; 
end; 
procedure inkq; 
var f:text; 
 i:integer; 
begin 
 assign(f,fo); rewrite(f); 
 for i:=1 to dem do writeln(f,p[i],' ',x[i]); 
 close(f); 
42 
end; 
BEGIN 
 readfile; 
 xuly; 
 inkq; 
END. 
Bài 2. Biểu diễn số 
Cho một số nguyên k, hãy tìm cách biểu diễn k thành tổng 3 số nguyên tố 
đôi một khác nhau. 
Dữ liệu : Vào từ file văn bản PRIME.INP chứa duy nhất 1 số là k 
(15<=k<=2.000.000.000). 
Kết quả : Ghi ra file văn bản PRIME.OUT gồm 3 số nguyên tố đôi một khác 
nhau và có tổng là k. 
Ví dụ : 
PRIME.INP PRIME.OUT 
15 3 5 7 
Chương trình: 
const 
 fi ='prime.inp'; 
 fo ='prime.out'; 
var n,m,k :longint; 
 f,g :text; 
procedure ndl; 
begin 
 readln(f,n); 
end; 
function ktnt(x:longint):boolean; 
var l:longint; 
begin 
 ktnt:=false; 
43 
 for l:=2 to trunc(sqrt(x)) do 
 if x mod l= 0 then exit; 
 ktnt:=true; 
end; 
procedure cb; 
begin 
 if n mod 2 =0 then k:=2 
 else k:=3; 
end; 
procedure xuli; 
var i:longint; 
begin 
 for i:=2 to n-2 do 
 if ktnt(i) then 
 if ktnt(n-k-i) then 
 begin 
 write(g,k,#32,i,#32,n-i-k); 
 writeln(g); 
 exit; 
 end; 
end; 
BEGIN 
 assign(f,fi); 
 reset(f); 
 assign(g,fo); 
 rewrite(g); 
 while not seekeof(f) do 
 begin 
 ndl; 
 cb; 
44 
 xuli; 
 end; 
 close(f); 
 close(g); 
END. 
Bài 3. Dãy nguyên tố 
Cho số tự nhiên k và dãy A gồm N (N < 104) số tự nhiên không vượt quá 
32000. 
Yêu cầu: Tìm k số nguyên tố nhỏ nhất khác nhau xuất hiện trong dãy A. 
Dữ liệu vào từ file văn bản DAYNT.INP: 
 Dòng đầu tiên chứa một số tự nhiên k (1< k < N). 
 N dòng tiếp theo, mỗi dòng chứa một số tự nhiên là một phần tử của 
dãy A. 
Kết quả ghi ra file văn bản DAYNT.OUT: Đưa ra trên cùng một dòng k số 
nguyên tố tìm được theo thứ tự tăng dần, các số cách nhau ít nhất một ký tự 
trống. 
Lưu ý: Dữ liệu vào đảm bảo luôn tìm được k số nguyên tố thỏa mãn. 
Ví dụ: 
DAYNT.INP DAYNT.OUT 
3 
12 
13 
6 
17 
9 
3 
1 
12 
3 13 17 
Chương trình: 
CONST fi = 'DayNT.inp'; 
 fo = 'DayNT.out'; 
45 
Var D : Array[2..32000] of byte; 
 i,n,k,a : integer; 
Procedure mofile; 
begin 
 assign(input,fi); 
 reset(input); 
 assign(output,fo); 
 rewrite(output); 
end; 
Function Nto( n : integer): boolean; 
var i :integer; 
begin 
 if n<2 then exit(false) 
 else 
 for i:=2 to trunc(sqrt(n)) do 
 if n mod i =0 then exit(false); 
 exit(true); 
end; 
Procedure Doc_xuly; 
begin 
 readln(k); 
 for i :=1 to 32000 do d[i] :=0; 
 while not seekeof do 
 begin 
 readln(a); 
 if nto(a) then d[a] :=1; 
 end; 
end; 
Procedure xuat; 
begin 
 n:=0; 
46 
 for i :=1 to 32000 do 
 if d[i] 0 then 
 begin write(i,' '); 
 n := n+1; 
 if n = k then exit; 
 end; 
end; 
Begin 
 mofile; 
 Doc_xuly; 
 xuat; 
end. 
Bài 3. Phân tích số 
Với số nguyên dương x, gọi f(x,k) là số cách phân tích số x thành tổng các 
số nguyên tố mà mỗi số nguyên tố có trong tổng không quá k lần. 
 ví dụ 
 f(12,3) =5 vì có 5 cách phân tích: 
 12 = 2 + 2 + 2 + 3 + 3; 12 = 2 + 2 + 3 + 5; 12 = 2 + 3 + 7; 
 12 = 2 + 5 + 5; 12 = 5 + 7 
 f(12,1) =2 vì có 2 cách phân tích 
 12 = 2 + 3 + 7; 12 = 5 + 7 
 Cho một dãy số nguyên dương a1,a2,,aN và số nguyên dương k( 1≤ N,k ≤ 
100). Hãy tính các f(ai,k) (với mọi i=1,2,,N). 
 Dữ liệu vào: Từ file văn bản KSNT.INP. có cấu trúc như sau: 
 Dòng đầu tiên ghi 2 số nguyên dương theo thứ tự N, k. 
 Dòng thứ 2 ghi N số nguyên dương a1, a2,, aN.( 1 < aI ≤ 100) 
 Kết quả: Ghi ra file văn bản KSNT.OUT, gồm N số nguyên viết trên một 
dòng, số thứ i là f(ai,k). 
 Cả 2 file dữ liệu thứ tự các số trên một dòng tính từ trái qua phải và cách 
nhau một dấu cách. 
 Ví dụ: 
47 
KSNT.INP KSNT.OUT 
5 6 
15 8 9 23 47 
12 3 4 35 414 
Chương trình: 
const 
 tfi='KSNTO.INP'; 
 tfo='KSNTO.OUT'; 
 maxMN=100; 
 NTO: array[1..25] of integer=( 2, 3, 5, 7,11,13,17,19,23,29, 
 31,37,41,43,47,53,59,61,67,71, 
 73,79,83,89,97); 
var 
 fi,fo: text; 
 M,N,k: integer; 
 a: array[1..100] of integer; 
 x,y: array[0..100] of real; 
procedure Docdl; 
var i,j: integer; 
begin 
 readln(fi,n,k); 
 for i:=1 to N do read(fi,a[i]); 
end; 
procedure ChuanBi; 
var i,j,l: integer; 
begin 
 for i:=0 to 100 do x[i]:=0; {khong xac dinh} 
 for j:=0 to k do 
 begin 
48 
 if j*NTO[1]>100 then break; 
 x[j*NTO[1]]:=1; 
 end; 
 for l:=2 to 25 do 
 begin 
 y:=x; 
 for i:=1 to 100 do 
 begin 
 x[i]:=0; 
 for j:=0 to k do 
 begin 
 if i-j*NTO[l]<0 then break; 
 x[i]:=x[i]+y[i-j*NTO[l]]; 
 end; 
 end; 
 end; 
end; 
procedure Inkq; 
var i,j: integer; 
begin 
 for i:=1 to N do write(fo,x[a[i]]:0:0,' '); 
end; 
BEGIN 
 assign(fi,tfi); reset(fi); 
 assign(fo,tfo); rewrite(fo); 
 Docdl; 
 ChuanBi; 
 Inkq; 
 close(fi); close(fo); 
49 
END. 
Bài 5. Số ước 
Cho số nguyên dương N. Giai thừa của N, kí hiệu là N!, là tích của các số tự 
nhiên từ 1 đến N. Gọi T là số lượng ước lớn hơn 1 của N!. Ví dụ với N = 4, ta có 
4! = 24. Như vậy 4! có 7 ước lớn hơn 1 là: 2, 3, 4, 6, 8, 12, 24. 
Yêu cầu: Cho N, hãy xác định T. 
Dữ liệu: Vào từ file văn bản DIVISORS.INP trong đó chứa duy nhất số N (N
20, trong đó 50% số test có N10). 
Kết quả: Ghi ra file văn bản DIVISORS.OUT số T tìm được. 
Ví dụ: 
DIVISORS.INP DIVISORS.OUT 
4 7 
Hướng dẫn: 
Nếu một số nguyên m được phân tích ra thừa số nguyên tố dưới dạng 
m=p1a1p2a2...pkak thì số ước số của m bằng tích (a1+1)(a2+1)...(ak+1). Ta sẽ tìm 
cách phân tích n! ra thừa số nguyên tố. Các ước số nguyên tố của n! chỉ nằm 
trong phạm vi từ 2 đến n, do đó ta duyệt qua tất cả các số nguyên tố trong 
phạm vi này. Với số nguyên tố p, số mũ của nó trong biểu diễn nguyên tố của n! 
bằng: 
[n/p] + [n/p2] + [n/p3] + ... 
Trong đó [n/p] ký hiệu phần nguyên của n/p, nói cách khác trong ngôn ngữ 
Pascal [n/p] bằng n div p. Công thức trên được giải thích như sau: [n/p] là số 
lượng số từ 1 đến n chia hết cho p, [n/p2] là số lượng số từ 1 đến n chia hết cho 
p2,... mỗi số này đều đóng góp một thừa số nguyên tố p phân biệt cho n!. 
Chương trình: 
const fi='DIVISORS.INP'; 
 fo='DIVISORS.OUT'; 
function nguyento(n: longint): boolean; 
var i: longint; 
begin 
 nguyento:=false; 
 for i:=2 to trunc(sqrt(n)) do 
 if n mod i = 0 then exit; 
50 
 nguyento:=true; 
end; 
var 
 n,i,j,a,d: longint; 
 f:text; 
begin 
 assign(f,fi); 
 reset(f); 
 readln(F,n); 
 d:=1; 
 for i:=2 to n do if nguyento(i) then 
 begin 
 a:=0; 
 j:=i; 
 while (j<=n) do 
 begin 
 a:=a+n div j; 
 j:=j*i; 
 end; 
 d:=d*(a+1); 
 end; 
 close(f); 
 assign(f,fo); 
 rewrite(f); 
 writeln(f,d-1); 
 close(f); 
end. 
51 
KẾT QUẢ ÁP DỤNG 
 Nội dung của đề tài là tập hợp các kiến thức thuật toán về số nguyên tố và 
vận dụng nó trong việc giải một số bài toán mà tác giả đã tích lũy được trong 
nhiều năm giảng dạy. 
 Đề tài này đã được áp dụng giảng dạy ở các lớp chuyên Tin, các lớp không 
chuyên tại trường THPT chuyên Phan Bội Châu; đồng thời cũng chia sẻ, trao đổi 
với một số giáo viên các trường THPT của tỉnh Nghệ An và đã thu được kết quả 
tốt. Các em học sinh học tập tích cực hơn, hứng thú hơn và đạt kết quả cao 
trong học tập cũng như trong các kỳ thi HSG môn Tin học. 
KẾT LUẬN 
 Trên đây là những kinh nghiệm mà tôi đã nghiên cứu vận dụng trong quá 
trình giảng dạy thực tế. Thông qua một số bài tập trên, học sinh được rèn luyện 
cách vận dụng các thuật toán về số nguyên tố để giải các bài toán. Từ đó các 
em có những kinh nghiệm vận dụng linh hoạt một thuật toán rất cơ bản vào 
từng bài toán cụ thể. Để đề tài của tôi được hoàn thiện hơn, việc sử dụng đạt 
hiệu quả cao hơn, tôi rất mong các thầy cô và các đồng nghiệp đóng góp ý kiến 
để việc giảng dạy trong nhà trường ngày càng hiệu quả hơn, giúp các em học 
sinh học tốt hơn. 
 Tôi xin chân thành cảm ơn! 
 Vinh, ngày 02 tháng 4 năm 2019 
 Tác giả 
 Phạm Thị Thu Hường 
52 
TÀI LIỆU THAM KHẢO 
1. Hồ Sĩ Đàm - Hồ Cẩm Hà - Trần Đỗ Hùng - Nguyễn Đức Nghĩa - Nguyễn 
Thanh Tùng - Ngô Ánh Tuyết. Tin học 11 (Sách giáo khoa) - NXB Giáo 
dục. 
2. Hồ Sĩ Đàm - Hồ Cẩm Hà - Trần Đỗ Hùng Nguyễn Đức Nghĩa – Nguyễn 
Thanh Tùng - Ngô Ánh Tuyết. Tin học 11 (Sách giáo viên) - NXB Giáo 
dục. 
3. Hồ Sĩ Đàm - Nguyễn Thanh Tùng - Ngô Ánh Tuyết. Tin học 11 (Sách bài 
tập) - NXB Giáo dục. 
4. Hồ Sĩ Đàm – Đỗ Đức Đông - Lê Minh Hoàng - Nguyễn Thanh Hùng. Tài 
liệu chuyên Tin học (Quyển 1, 2) - NXB Giáo dục. 
5. Bài giảng của Lê Minh Hoàng – ĐHSP Hà nội. 
6. Một số đề thi chọn HSG THPT, đề thi Trại hè Hùng Vương, 
7. Bài tập trên https://vn.spoj.pl/problem