Các bài toán phân tích số
Cao Minh Anh
Trong quá trình học chắc các bạn sẽ gặp rất nhiều các bài toán về phân tích số. Các bài này
có rất nhiều dạng khác nhau. Sau đây tôi xin đề cập đến một số bài toán để cùng trao đổi
với các bạn.
Bài 1: Cho số nguyên dương M(M<=2
32
),tìm cách phân tích M ra các số nguyên dương
khác nhau có tổng bằng M sao cho tích của chúng là lớn nhất.
Mart.inp
M
Mart.out
a1 a2 a3 … ak
Ví dụ:
Mart.inp
11
Mart.out
2 4 5
Với bài toán trên thì có nhiều cách giải khác nhau,sau đây tôi xin trình bày với các bạn một
thuật toán để giải bài này có tính mô phỏng. Đó là “thuật toán rải đậu”.
Sau đây tôi xin trình bầy tư tưởng thuật toán như sau:
Thuật toán:
+Xây dựng mảng a với a[1]=2;
a[I]=a[I-1]+1;(I>=2)
Tìm k lớn nhất sau cho a[1]+a[2]+..+a[k]<=M;
+ Xét d:=M-(a[1]+a[2]+..+a[k]);
+ Bây giờ ta tưởng tượng ta đang có d hạt đậu, chúng ta bắt đầu rải từng hạt đậu vào các
a[I](1<=I<=k) theo chiều từ k1. Nếu rải đến 1 mà vẫn còn thì ta vẫn rải lại bắt đầu từ k
lại,cứ như thế cho đến khi không còn hạt đậu nào. Khi rải đậu đến ô nào thì tăng giá trị của
ô đó lên.
Sau đó xuất mảng a[i] ra là giải quyết xong bài toán.

end;
procedure closef;
begin
close(f);
close(g);
end;
procedure Init;
begin
readln(f,m);
end;
procedure Timk;
begin
delta:=1+8*(M+1);
k1:=((-1)-sqrt(delta))/2;
k2:=((-1)+sqrt(delta))/2;
k:=trunc(k2);
du:=M+1-(k*(k+1) div 2);
end;
procedure Print;
var i:longint;
begin
k:=k-1;
cs:=du div k;
sp:=du mod k;
r:=2;
for i:=1 to k-sp do
begin
write(g,r+cs,' ');
r:=r+1;
if i mod 100=0 then writeln(g);

begin
Nto:=false;
For i:=2 to round(sqrt(n)) do
If n mod i=0 then exit;
Nto:=true;
End;
Procedure Print;
Var i:integer;
Begin
For i:=1 to dem do write(g,a[i]:4);
Writeln(g);
End;
Procedure Phantich(n,k,d:integer);
Begin
A[d]:=k;
If n=0 then
Begin
Dem:=d;
Print;
End
Else
Begin
For i:=k to n do
If nto(i) then phantich(n-i,i,d+1);
N:=n+k;
End;
End;
Từ bài trên có thể chuyển qua rất nhiều bài như sau:
+Phân tích n ra các số nguyên tố khác nhau.
Chỉ cần sửa một chút là:

Khởi tạo: Fx[i]=1 nếu i là số nguyên tố.
Khi xét các số nguyên tố p từ 2..n thì ta luôn có:
Fx[j]:=Fx[j]+Fx[j-p];
for i:=2 to n do
if nto(i) then
begin
Fx[i]:=Fx[i]+1;
for j:=i+2 to n do
Fx[j]:=Fx[j]+Fx[j-i];
end;
Đây là chương trình chính:
uses crt;
const fi='Prime.inp';
go='Prime.out';
type arr=array[1..50] of byte;