1

mở đầu
Nếu như trước thập niên 70 của thế kỉ XX, Số học vẫn được xem
là một trong những ngành lí thuyết xa rời thực tiễn nhất, thì ngày nay
nhiều thành tựu mới của Số học đã có ứng dụng trực tiếp vào các vấn đề
của cuộc sống như thông tin, mật mã, kĩ thuật máy tính. Một phương
hướng mới đã ra đời và phát triển mạnh mẽ: Số học thuật toán. Đây
là một ngành toán học nghiên cứu về các nội dung số học trên cơ sở
sử dụng công cụ thuật toán. Số học là một trong những ngành toán cổ
nhất, còn Thuật toán lại là một khái niệm mới mẻ, ra đời và phát triển
trong thế kỉ XX. Do đó, có thể nói Số học thuật toán chính là chiếc cầu
nối giữa Số học và Thuật toán, và nó được xây dựng trên cơ sở những
thành tựu của Toán - Tin học.
Một trong những bài toán nổi tiếng nhất đã được giải quyết trong
thế kỉ XX là bài toán thứ 10 của Hilbert "Có tồn tại một thuật toán
tổng quát cho phép ta trả lời một phương trình Diophante cho trước có
nghiệm nguyên hay không?". Bài toán này đã được nhà toán học người
Nga, Michiakêvích, giải quyết trọn vẹn vào năm 1970 với câu trả lời
phủ định, tức là không có một thuật toán như vậy. Bài toán thứ 10 của
Hilbert được giải quyết là một thành tựu quan trọng của Số học cũng
như Thuật toán.
Số học thuật toán không chỉ phát triển trên những thành tựu của
Số học sơ cấp, mà nó còn tận dụng những thành tựu cua Số học hiện
đại, Đại số hiện đại, ... Cũng như những ngành toán học khác, trong Số
học thuật toán cũng có những bài toán NP, tức là không có một thuật
toán giải trong thời gian đa thức, tiêu biểu là các bài toán: Phân tích
một số nguyên ra thừa số nguyên tố, thuật toán kiểm tra số nguyên tố,
thuật toán chuyển đĩa trong Bài toán Tháp Hà Nội.
Trong luận văn này, tôi chỉ đề cập đến những vấn đề cơ sở nhất của
Số học thuật toán, bao gồm những nội dung chính sau:

Nghệ An, tháng 02 năm 2012
Tác giả
Nguyễn Thành Trung


3

chương 1
một số kiến thức cơ sở
1.1. Thuật toán
1.1.1. Thuật toán. Có thể định nghĩa thuật toán theo nhiều cách khác
nhau, ở đây chúng tôi không trình bày chặt chẽ về thuật toán như trong
một giáo trình logic, mà sẽ hiểu khái niệm thuật toán theo một cách
thông thường nhất.
Thuật toán là một quy tắc để với những dữ liệu ban đầu đã cho, ta
tìm được lời giải sau một thời gian hữu hạn.
Có thể nói rằng, một thuật toán cần phải thỏa mãn các yêu cầu sau
đây:
[1]. Tính hữu hạn. Thuật toán cần phải kết thúc sau một số hữu hạn
bước. Khi thuật toán ngừng làm việc, ta phải thu được câu trả lời cho
vấn đề đặt ra.
[2]. Tính xác định. ở mỗi bước, thuật toán cần phải xác định, nghĩa là
chỉ rõ ra việc cần làm.
Ngoài ra, ta còn phải xét đến tính hiệu quả của thuật toán. Có rất
nhiều thuật toán, về mặt lí thuyết là kết thúc sau hữu hạn bước, tuy
nhiên thời gian "hữu hạn" đó vượt quá khả năng làm việc của chúng
ta. Những thuật toán như vậy sẽ không được xét ở đây vì chúng tôi chỉ
quan tâm những thuật toán có thể sử dụng thật sự trên máy tính.
Cũng do mục tiêu nói trên, chúng ta cần phải chú ý đến độ phức
tạp của thuật toán. Độ phức tạp của thuật toán có thể đo bằng không


ai để với n đủ lớn thì f (n), g (n) đều dương và
i=1

f (n) < C.g (n).
1.1.3. Tính chất của bậc O-lớn. Ta có những tính chất sau đây:
[1]. Nếu f1 = O (g ) và f2 = O (g ) thì f1 + f2 = O (g ).
[2]. Nếu f1 = O (g1 ) và f2 = O (g2 ) thì f1 f2 = O (g1 g2 ).
f (n)
[3]. Nếu tồn tại giới hạn hữu hạn lim
thì f = O(g ).
n→∞ g (n)
[4]. Với mọi > 0, ta luôn có logn = O (n ).
1.1.4. Định nghĩa. Một thuật toán được gọi là có độ phức tạp đa thức
nếu số các phép tính cần thiết khi thực hiện thuật toán đó không vượt
quá O(log d n), trong đó n là độ lớn của đầu vào và d là số nguyên dương
nào đó.
Nói cách khác, nếu đầu vào là các số k-bit thì thời gian thực hiện
thuật toán là O(k d ), tức là tương đương với một đa thức của k.
1.2. Số nguyên
1.2.1. Định lí. Giả sử b là một số nguyên lớn hơn 1. Khi đó mọi số
nguyên n có thể được viết duy nhất dưới dạng
n = ak bk + ak−1 bk−1 + ... + a1 b + a0
trong đó aj là các số nguyên, 0 ≤ aj ≤ b − 1, j = 0, 1, 2, ..., k và hệ số đầu
tiên ak = 0.
Số b nói trong định lí 1.2.1 được gọi là cơ số biểu diễn. Các hệ biểu
diễn cơ số 10 và 2 tương ứng được gọi là hệ thập phân và hệ nhị phân.
Các hệ số aj được gọi là các chữ số. Về sau ta dùng bit để chỉ chữ số
trong hệ nhị phân.
Nếu số nguyên n biểu diễn trong cơ số b có k chữ số thì từ chứng

Chứng minh. Thật vậy, vì n là hợp số nên ta gọi a và b là các ước thật
sự của n. Khi đó n = ab,√trong đó 1 < a ≤ b < n. Rõ ràng ta phải có a
hoặc b không vượt quá n, giả sử đó là a. Khi đó, ước nguyên tố của a
cũng đồng thời là ước nguyên tố của n.
Từ định lí 1.2.3, ta có thuật toán tìm ra các số nguyên tố nhỏ hơn
hoặc bằng số nguyên dương n cho trước.
1.2.4. Thuật toán sàng các số nguyên tố của Eratosthenes. Trước
tiên, ta viết dãy các số tự nhiên từ 1 đến n. Trong dãy đó, ta gạch bỏ số
1 vì nó không phải là số nguyên tố. Số nguyên tố đầu tiên của dãy là số
2. Tiếp theo đó ta gạch khỏi dãy số tất cả những số chia hết cho 2. Số
đầu tiên không chia hết cho 2 là 3: đó chính là số nguyên tố. Ta lại gạch
khỏi dãy số còn lại những số nào không chia hết cho 3. Ta thu được số
nguyên tố tiếp theo là 5. Tiếp tục như√thế, ta gạch khỏi dãy những số
chia hết cho mọi số nguyên tố bé hơn n.
Sàng Eratosthenes mặc dù cho ta thuật toán xác định mọi số nguyên
tố không vượt quá một số cho trước nhưng lại rất ít được sử dụng để
xác định xem một số đã cho có phải là số nguyên tố hay không. Nguyên
nhân là vì thuật toán có độ phức tạp khá lớn: để kiểm tra n, ta
√ phải
thực hiện phép chia cho tất cả các số nguyên tố không vượt quá n.
1.2.5. Định lí cơ bản của Số học. Mọi số nguyên lớn hơn 1 đều phân
tích được một cách duy nhất thành tích các số nguyên tố, trong đó các
thừa số được viết với thứ tự không giảm.
1.3. Quan hệ đồng dư
1.3.1. Định nghĩa. Giả sử m là một số nguyên dương. Ta nói hai số
nguyên a và b là đồng dư với nhau modulo m nếu m chia hết hiệu a - b.


6
Để chỉ quan hệ đồng dư, ta dùng kí hiệu a ≡ b(mod m).

≡ 1(mod n) thì có suy ra được n là số nguyên tố hay không? Câu
trả lời là phủ định.
Thật vậy, ta có: 2560 = (22 )280 ≡ 1(mod 3), 2560 = (210 )56 ≡ 1(mod 11)
và 2560 = (216 )35 ≡ 1(mod 17). Do đó, 2560 ≡ 1(mod 561). Nhưng 561 không
là số nguyên tố vì 561 = 3.11.17. Như vậy, chiều ngược lại của định lí
Fermat bé là không đúng.
Tuy nhiên, nếu một số nguyên thỏa mãn các giả thuyết của định lí
Fermat bé thì "có nhiều khả năng" nó là số nguyên tố. Ta có định nghĩa
sau:
1.3.5. Định nghĩa
Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương
n
và b ≡ b(mod n) thì n được gọi là số giả nguyên tố cơ sở b.
Trong trường hợp (b, n) = 1, ta thường dùng định nghĩa tương đương
n−1
b
≡ 1(mod n).
Ví dụ: Vì 2560 ≡ 1(mod 561) nên 561 là số giả nguyên tố cơ sở 2.
1.3.6. Định lí. Có vô số số giả nguyên tố cơ sở 2.
Chứng minh. Giả sử n là một số giả nguyên tố cơ sở 2, ta sẽ chứng tỏ rằng
m = 2n − 1 cũng là số giả nguyên tố cơ sở 2. Thật vậy, theo giả thiết thì n


7
là hợp số nên ta giả sử n = dt (1 < d, t < n). Lại do: m = 2n − 1 = 2dt − 1
nên 2dt |(m + 1). Suy ra 2d |(m + 1). Do đó, 2d − 1|m. Vậy m là hợp số. Mặt
khác, do n là số giả nguyên tố nên 2n ≡ 2(mod n).
Do đó tồn tại số k sao cho 2n − 2 = kn. Ta có: 2m−1 = 2kn, và do đó,
m = (2n − 1)|(2nk − 1) = 2m−1 − 1, tức là 2m−1 ≡ 1(mod m).
Vậy m là số giả nguyên tố cơ sở 2.

thì hoặc bt ≡ 1(mod n) hoặc b2 t ≡ −1(mod n) với j nào đó thỏa điều
kiện 0 ≤ j ≤ s − 1.
1.3.10. Mệnh đề. Nếu n là số nguyên tố thì n trải qua được kiểm tra
Miller cơ sở b với mọi số b sao cho n là ước của b.
n−1
s−k
Thật vậy, giả sử n − 1 = 2s t. Ta đặt xk = b 2k = b2 t với k = 0, s.
Vì n là số nguyên tố nên theo định lí Fermat bé, ta được: x0 ≡ 1(mod
n−1
n). Khi đó, x1 = b 2 . Suy ra x21 = x0 ≡ 1(mod n), tức là x ≡ 1(mod n)


8
hoặc x ≡ −1(mod n). Tiếp tục quá trình như vậy, ta sẽ đi đến kết luận
rằng: hoặc xk ≡ 1(mod n) hoặc xk ≡ −1(mod n) với k = 0, s. Vậy n trải
qua được kiểm tra Miller cơ sở b.
Dễ thấy rằng, nếu n trải qua được kiểm tra Miller thì n là số giả
nguyên tố cơ sở b. Ta có định nghĩa sau:
1.3.11. Định nghĩa. Số nguyên n được gọi là số giả nguyên tố mạnh
cơ sở b nếu nó là hợp số và trải qua được kiểm tra Miller cơ sở b.
Như vậy, các số giả nguyên tố mạnh còn ít hơn các số giả nguyên
tố. Tuy nhiên, ta có định lí sau đây:
1.3.12. Định lí. Tồn tại vô số số giả nguyên tố mạnh cơ sở 2.
Thật vậy, giả sử n là một số giả nguyên tố cơ sở 2. Khi đó, với số
nguyên lẻ nào đó, ta có 2n−1 − 1 = nk. Đặt N = 2n − 1, khi đó nó có ước
là 2d − 1 với d là ước nào đó của n. Mặt khác:
N −1
N − 1 = 2n − 2 = 2(2n−1 − 1) = 2nk và 2 2 = 2nk = (2n )k ≡ 1(mod N ).
Vậy với mỗi số giả nguyên tố n, ta xây dượng được số giả nguyên tố
mạnh N và các số n khác nhau cho ta các số N khác nhau. Định lí này


. Khi đó với

k đủ lớn, ví dụ k = 20, xác suất đó quá nhỏ, nên với n trải qua với 20
cơ sở ngẫu nhiên thì có thể tin "hầu chắc chắn" rằng n là số nguyên tố.
1.3.14. Định nghĩa. Phi hàm Euler, kí hiệu là φ(n), là hàm số học có
giá trị tại n bằng số các số không vượt quá n và nguyên tố cùng nhau
với n.


9
1.3.15. Định lí Euler. Nếu m là số nguyên dương và a là số nguyên tố
cùng nhau với m thì aφ(m) ≡ 1(mod m), trong đó φ là hàm số học Euler.
Định lí Euler có thể dùng để tìm nghịch đảo modulo m. Chẳng hạn,
nếu a và m là các số nguyên tố cùng nhau, ta có aaφ(m)−1 ≡ 1(mod m),
tức là aφ(m)−1 là nghịch đảo của a modulo m. Từ đó cũng suy ra nghiệm
của phương trình đồng dư tuyến tính ax ≡ b(mod m), với (a, m) = 1 là
x ≡ aφ(m)−1 b(mod m).
1.3.16. Định lí (Công thức phi hàm Euler). Giả sử n = pα1 1 pα2 2 ...pαk k là
phân tích của n thành thừa số nguyên tố. Khi đó, ta có:
φ(n) = n 1 −

1

1−

1

... 1 −


- Về mặt dữ liệu,
- Về mặt lênh,
- Về mặt chương trình.
Thuật giải và chương trình:
- Thuật giải: Là tập hợp hữu hạn các thao tác (các bước thực hiện
các công việc.)
- Chương trình: Là tập hợp các lệnh điều khiển máy tính thực hiện.
2.2. Một số thuật toán số học được lập trình bằng ngôn ngữ
Pascal
2.1.1. Thuật toán chuyển một số nguyên dương từ hệ thập phân
sang hệ nhị phân
- Thuật toán
[B1 ] Nhập số nguyên dương n.
[B2 ] Nếu n ≤ 1 thì in ra kết quả. Ngược lại thực hiện [B3 ].
[B3 ] Thực hiện phép chia n cho 2, ta được thương là r1 . Tiếp tục thực
hiện phép chia r1 cho 2, ta được thương r2 . Rồi lại lấy r2 chia cho 2, ta
được thương r3 .... Quá trình trên kết thúc ở bước thứ i nào đó với ri = 0
(i = 1, 2, 3, ...). Khi đó, hiển thị kết quả.
- Lập trình cụ thể
Program Chuyen mot so nguyen duong tu thap phan sang nhi phan;
Var
d: array[1..20] of Byte;
i, j, n: Integer;
Begin
Write(’Nhap so thap phan la n =’);
Readln(n);
i:=1;
Repeat
d[i]:= n mod 2;


Else a[i]:=0;
n:=0;
For i:=1 to length(S) do
Begin
gt:=1;
For k:=1 to length(s)-i do
gt:=gt*2;
n:=n + a[i]*gt;
End;
Write(’So thap phan la: ’,n);
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.


12
2.2.3. Thuật toán tìm tất cả các ước dương của một số nguyên
dương
- Thuật toán
[B1 ] Nhập số nguyên dương n.
[B2 ] Thực hiện liên tiếp các phép chia n cho i với i là các số nguyên
n
dương không vượt quá . Mỗi phép chia có số dư bằng 0 thì ta tìm được
2

một ước i của n.
[B3 ] Hiển thị kết quả.
- Lập trình cụ thể
Program Tim uoc nguyen duong;
Var


13
For i:= 2 to trunc(sqrt(n)) do
If n mod i = 0 then exit;
ngto:= true;
End;
Begin
Writeln(’Kiem tra tinh nguyen to cua mot so nguyen duong’);
Writeln(’...............................................’);
Write(’Nhap so nguyen duong can kiem tra, n = ’);
Readln(n);
If ngto(n) = true then
Writeln(n,’ la so nguyen to.’)
Else
Writeln(n,’ khong la so nguyen to.’);
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.5. Thuật toán tìm tất cả các số nguyên tố không vượt quá
số nguyên dương n
- Thuật toán
[B1 ] Nhập số nguyên dương n.
[B2 ] Kiểm tra tính nguyên tố của số nguyên dương i không vượt quá n.
[B3 ] In ra kết quả nếu i là số nguyên tố.
- Lập trình cụ thể
Program Tim tat cac so nguyen to khong vuot qua so nguyen duong n;
Var
i, j, n : integer;
ngto: boolean;
Begin

s := 0;
For i := 1 to (n div 2) do
If n mod i = 0 then s := s + i;
tongus := s;
End;
Begin
Writeln(’Kiem tra so hoan chinh’);
Writeln(’.................................’);
Write(’Nhap so tu nhien ma ban muon kiem tra, n = ’);
Readln(n);
tongcantim := (tongus(n) + n);
If tongcantim = (2*n) then
Writeln(n,’ la so hoan hao.’)
Else
Writeln(n,’ khong la so hoan hao.’);
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.7. Thuật toán tìm tam giác Pascal
- Thuật toán
[B1 ] Nhập số dòng muốn hiển thị của tam giác Pascal, n.
[B2 ] Phần tử thứ i của dòng thứ k (trừ phần tử đầu và phần tử cuối của
dòng k) bằng tổng của hai phần tử thứ i − 1 và i của dòng thứ k − 1
(k ≤ n).
- Lập trình cụ thể
Program Tim tam giac Pascal;
Var


15

Var
n, kq: integer;
Function F(n: integer): longint;
Begin
If ((n=1) OR (n=2)) then
F:= 1
Else
F:= F(n - 1)+F(n - 2);
End;
Begin
Writeln(’Tim so hang thu n trong day so Fibonacci:’);


16
Writeln(’...............................................................’);
Write(’Ban muon tim so hang dung o vi tri thu n = ’);
Readln(n);
Writeln(’F(’,n,’)= ’,F(n), ’.’);
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.9. Thuật toán tìm ước chung lớn nhất và bội chung nhỏ
nhất của hai số nguyên dương
- Thuật toán
[B1 ] Nhập hai số nguyên dương cần tìm UCLN, BCNN a và b.
[B2 ] Giả sử a > b. Thực hiện phép chia a cho b, ta được số dư r. Tiếp
tục thực hiện phép chia b cho r, ta được số dư r1 . Rồi lại chia r cho r1 .....
Quá trình này sẽ kết thúc ở bước thứ i nào đó với số dư ri−1 = 0. Khi
đó, UCLN(a, b) = ri−2 và BCN N (a, b) = a ∗ b div U CLN (a, b).
- Lập trình cụ thể

2.2.10. Thuật toán tính giai thừa của một số tự nhiên
- Lập trình cụ thể
Program Tinh giai thua;
Var
i, n: integer;
s: longint;
Function giaithua(n : integer) : longint;
Begin
s := 1;
For i := 2 to n do s := s * i;
giaithua := s;
End;
Begin
Writeln(’Tinh giai thua cua mot so tu nhien’);
Writeln(’......................................................’);
Write(’Nhap so tu nhien can tinh giai thua, n =’);
Readln(n);
Writeln(n,’ ! = ’,giaithua(n));
Writeln(’Nhan Enter de ket thuc chuong trinh’);
Readln;
End.
2.2.11. Thuật toán tìm tất cả các số nguyên tố trong một dãy
số nguyên dương nhập vào từ bàn phím
- Lập trình cụ thể
Program Tim tat ca cac so nguyen to cua mot day so nhap tu ban phim;
Var
n : integer;
a : array[1..100] of integer;
Procedure nhap;
Var i : integer;

Procedure inngto;
Var i, kiemtranguyento : integer;
Begin
Writeln(’Cac pha tu nguyen to trong day la: ’);
kiemtranguyento:= 0;
For i := 1 to n do
If ngto(a[i]) then writeln(’a’,i,’= ’,a[i])
Else kiemtranguyento := kimtranguyento + 1;
If kiemtranguyento = n then
Writeln(’Day so khong co phan tu nao la so nguyen to.’);
End;
Begin
Writeln(’Tim tat ca cac so nguyen to trong mot day so’);
Writeln(’.......................................................................’);
nhap;
inngto ;
Writeln;
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
readln;
End.
2.2.12. Thuật toán tìm ước chung lớn nhất của tất cả các phần
tử trong một dãy số nguyên dương nhập từ bàn phím
- Lập trình cụ thể
Program Tim UCLN cua tat ca cac phan tu trong mot day so nguyen


19
duong;
Var
n : integer;

End;
UCLN := a;
End;
Procedure TinhUCLN;
Var i,u : integer;
Begin
u := a[1];
For i := 2 to n do u := UCLN(u,a[i]);
Writeln(’UCLN cua ca day la: ’,u);


20
End;
Begin
Writeln(’Tim UCLN cua tat ca cac phan tu trong mot day so nguyen
duong’);
Writeln(’.....................................................................................................’);
Nhap;
TinhUCLN;
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.13. Thuật toán tìm tất cả các phần tử chính phương trong
một dãy số nhập từ bàn phím
- Lập trình cụ thể
Program Tim tat ca cac phan tu chinh phuong trong mot day so nguyen
duong;
Var
i, n : integer;
a : array[1..100] of integer;

Begin
Writeln(’Cac phan tu chinh phuong trong day la:’);
For i := 1 to n do
Begin
If chinhphuong(a[i]) Then writeln(’a’,i,’= ’,a[i]);
End;
End;
Begin
Writeln(’Tim tat ca cac phan tu chinh phuong trong mot day so’);
Writeln(’................................................................................’);
Nhap;
Inchinhphuong;
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.14. Sắp xếp một dãy số theo thứ tự tăng dần hoặc giảm dần
- Lập trình cụ thể
Program Sap xep day so;
Var
n : integer;
a : array[1..100] of longint;
Procedure Nhap;
Var i : integer;
Begin
Write(’So phan tu cua day la n = ’);
Repeat
Readln(n);
If (1< n) and (n
If a[i] < a[j] then
Begin
giam := a[i]; a[i] := a[j]; a[j] := giam;
End;
Writeln(’Day so sau khi sap xep giam dan la:’);
For i := 1 to n do writeln(a[i]);
End;
Begin
Writeln(’In mot day so theo thu tu tang dan hoac giam dan’);
Writeln(’............................................................................’);
Nhap;
Sapxeptang;
Sapxepgiam;
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.15. Thuật toán tìm tất cả các phần tử là số hoàn chỉnh
trong một dãy số nhập từ bàn phím
- Lập trình cụ thể
Program Tim tat ca cac so hoan hao cua mot day so nhap tu ban phim;
Var
i, n : integer;
a : array[1..100] of integer;


23
Procedure nhap;
Begin
Write(’So phan tu cua day la n = ’);
Repeat

Var kiemtrahoanhao: integer;
Begin
Writeln(’Cac phan tu la so hoan hao trong day la:’);
kiemtrahoanhao := 0;
For i := 1 to n do
Begin
If hoanhao(a[i]) then writeln(’a’,i,’= ’,a[i]);
Else kiemtrahoanhao := kiemtrahoanhao + 1;


24
If kiemtrahoanhao = n then
Writeln(’Day so khong co phan tu nao la so hoan hao.’);
End;
End;
Begin
Writeln(’Tim cac phan tu la so hoan hao trong mot day so’);
Writeln(’..........................................................................’);
Nhap;
inhoanhao;
Writeln;
Writeln(’Nhan Enter de ket thuc chuong trinh.’);
Readln;
End.
2.2.16. Phân tích một số nguyên dương ra thừa số nguyên tố
- Thuật toán
[B1 ] Nhập số nguyên dương cần phân tích n.
[B2 ] Chia n cho số nguyên tố u (số nguyên tố nhỏ nhất là 2). Trong khi
n còn chia hết cho u thì tiến hành phân tích n. Sau mỗi lần chia, n giảm
đi u lần.

If n > 1 then
Begin
u := 2;
dem := 0;
While ( n > 1 ) do
If ( n mod u = 0 ) then
Begin
dem:= dem + 1;
Writeln( u);
n := n div u;
End
Else
u:= u + 1;
End;
End;
Begin
Writeln(’Phan tich so ngyen duong n thanh tich cua cac so nguyen to :’
);
Writeln(’..........................................................................’);
NhapSo(n);
Writeln(’Ket qua phan tich la: ’);
PhantichSo(a[i]);
Writeln (’Nhan Enter de ket thuc chuong trinh.’ );
Readln;
End.
2.2.17. Sàng Eratosthenes để tìm tất cả các số nguyên tố không
vượt quá một số nguyên dương cho trước
- Ý tưởng
Ta lập một dãy các số nguyên dương từ 2 đến n mà tạm gọi đó là
sàng. Số nhỏ nhất trong dãy này (số 2) là số nguyên tố. Sau đó la loại