Tối ưu các bài toán về số nguyên tố
Đinh Hữu Công
Trong số 11-2001 tácgiả Nguyễn Văn Trường đã giới thiệu các thuật toán về số nguyên
tố.Nhưng một số thuật toán này còn bị hạn chế về thời gian và bộ nhớvới n lớn. Tuỳ vào
từng bài toán cụ thể ta có thể tối ưu hoá nhữngthuật toán này dựa vào những nhận xét và
chứng minh toán học.
Bài toán 1: Cho số tựnhiên n. Hãy phân tích số n thành tích các thừa số nguyên tố
Input: file Phantich.inp với số n duy nhất (n < 2
31
)
Ouput: file Phantich.out. Dòng 1 là k, số thừa số nguyên tố khác nhautrong phân tích. K
dòng tiếp theo dòng thứ i gồm 1 cặp số (p,q) cáchnhau 1 dấu trắng trong đó p là thừa số
nguyên tố và q là số mũ tươngứng của nó trong phân tích (q > 0).
Thuật toán của bài này rất đơn giản:
+ Cho biến chạy Temp=0,
+ Lặp: Chừng nào temp≤n thì làm
- Temp:=số nguyên tố liền sau Temp;
- While (n mod Temp=0) do
Begin
n:=n div Temp;
Tăng số mũ của Temp;
End;
Hiệuquả của cài đặt chủ yếu phụ thuộc vào công đoạn tìm số nguyên tốliền sau Temp.
Cách nhanh nhất là dùng 1 mảng để lưu trữ các số nguyêntố từ 1 đến n. Với n=1 tỷ ta phải
lưu (10
9
) = 50.847.534 số nguyên tố nên ta không thể có đủ bộnhớ để thực hiện điều này.
Một cách khác là ta tuần tự tăng biếnTemp và kiểm tra Temp có nguyên tố không, cách
này không tốn bộ nhớnhưng không khả thi vì thời gian thực hiện quá lâu. Một cách tự
nhiên,ta muốn dung hoà cả hai phương pháp trên. Vì vậy ta sẽ tìm cách giảmkhối lượng
lưu trữ và số lần kiểm tra nguyên tố:

Fillchar(Prime,sizeof(Prime),true);
Prime[0]:=false;
Prime[1]:=false;
for i:=2 to trunc(sqrt(maxPrime)) do
if Prime[i] then
for j:=2 to (maxPrime div i) do
Prime[i*j]:=false;
end;
functionisPrime(n:longint):boolean;
vari,step:word;
begin
isPrime:=false;
if (n
begin
if Prime[n] then isPrime:=true;
exit;
end;
if ((n mod 2=0) or (n mod 3=0)) then Exit;
i:=5;
step:=2;
while (i≤sqrt(n)) do
begin
if (n mod i=0) then
exit;
i:=i+step;
step:=6-step;
end;
isPrime:=true;
end;
procedureSolve;

Inc(temp);
while not Prime[temp] do
Inc(temp);
end;
Inc(count);
p[count]:=temp;
while (n mod temp=0) do
begin
Inc(q[count]);
n:=n div temp;
end;
end;
end;
end;
procedureResult;
vari:integer;
begin
Writeln(g,count);
for i:=1 to count do
Writeln(g,p[i],' ',q[i]);
Close(g);
end;
BEGIN
Eratosten;
Solve;
Result;
END.
Saukhi làm bài toán 1 ta sẽ dễ dàng làm được bài toán số 2 trong đềkhối 10 cuộc thi
Olympic 30-4 lần VIII.
Đề bài như sau:

2
, p
3
…trong khoảng
1..n. Dễ thấy số mũ của p là s
1
+s
2
+…+s
k
với k lớn nhất sao cho p
k
≤ n
Vídụ: n=29 vàp =3 thì k=3, s
1
=9, s
2
=3, s
3
=1 → Số mũ của 3 là s
1
+s
2
+s
3
=13
Mặtkhác các số chia hết cho p
i
trong khoảng 1..n là: 1* p
i

k
. Vì vậy hàm SoMu chỉ phải vào vòng lặp k lầnvới k là
số nguyên nhỏ nhất sao cho n < p
k

Cụthể trong bài này trường hợp lớn nhất là n = 2
31
; p = 2 thì
k = log
2
2
31
= 31 so với 2
30
(nhỏ hơn34 triệu lần) !
Bài toán 3: Tìm số chữ số 0 tận cùng và chữ số tận cùng khác 0 của n! (n< 2
31
). Dữ liệu
nhập từ bàn phím số n và in kết quả sốchữ số 0 tận cùng và chữ số tận cùng khác 0 của n!
ra màn hình
Cơsở thuật toán: Ta thấy n! khi phân tích ra thừa số nguyên tố thìcó dạng
n! = 2
SoMu(2,n)
* 5
SoMu(5,n)
*…
Trong công thức Lơgiăngđrơ nếu p
1
< p
2

while (tg mod 5=0) do
tg:=tg div 5;
temp:=temp*(tg mod 10) mod 10;
end;
temp:=temp mod 10;