Cho số tự nhiên n £ 480.000. 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ụ,
13! = 210.35.52.7.11.13. Kết quả hiển
thị dưới dạng các dòng, mỗi dòng một 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. Thí dụ trên cho ta kết quả hiển
thị như sau
2 10
3 5
5 2
7 1
11 1
13 1
Thuật toán
Nhận xét Cho số tự nhiên
N và một số nguyên tố p. Khi đó,
Nếu viết dãy thừa số 1, 2, ..., N vào một bảng có p cột thì
ta thấy có n1 = N div p dòng chứa p, 2p,...,n1.p (ở cột
cuối cùng). Nhóm các phần tử này lại ta được,
1p.2p....n1p = (1.2...n1).pn1.
Thực hiện tương tự với tích 1.2...n1 ta thu được n2 = n1
div p dòng chứa p, 2p,...,n2.p...
Từ đây ta suy ra lũy thừa k của p, pk trong dạng phân tích của N! sẽ
là k = n1+n2+...+nv, trong đó ni =
ni-1 div p, n1 = N div p, nv = 0, i = 2..v.
Hàm tính lũy thừa của p trong dạng phân tích của N! bằng các phép chia liên
tiếp khi đó sẽ như sau,
function Power(n,p: longint): byte;
var k: byte;
begin
k := 0;
while (n <> 0) do
begin
n := n div p;
k := k + n;
end;
Power := k;
end;
Ta dùng hàm NextPrime để sinh
lần lượt các số nguyên tố p trong khoảng 2..N và tính Power(N,p). Nếu giá
trị này lớn hơn 0 thì ta hiển thị kết quả.
procedure Fac(n: longint);
const bl = #32; { Dau cach }
var p: longint; k: byte;
begin
writeln;
p := 2;
while p <= n do
begin
k := Power(n,p);
if (k > 0) then
writeln(p,bl,k);
p := NextPrime(p);
end;
end;
Hai hàm phụ trợ.
Hàm IsPrime(p) kiểm tra p có phải là
số nguyên tố hay không bằng cách xét xem trong khoảng từ 2 đến có ước nào không.
function IsPrime(p: longint): Boolean;
var i: longint;
begin
IsPrime := false;
if p < 2 then exit;
for i := 2 to
round(sqrt(p)) do
if p mod i = 0 then
exit;
IsPrime := True;
end;
Hàm NextPrime(p) sinh số
nguyên tố sát sau p bằng cách duyệt tuần tự các số lẻ sau p là p+2k nếu p lẻ và
(p-1) + 2k, nếu p chẵn.
function NextPrime(p: longint): longint;
begin
if p < 2 then
begin
NextPrime := 2;
exit;
end;
if not odd(p) then p :=
p-1;
repeat
p := p+2;
until IsPrime(p);
NextPrime := p;
end;
Ta có thể cải tiến khá mạnh tốc độ tính toán bằng các kỹ
thuật sau.
Sinh sẵn các số nguyên tố trong khoảng từ 1..N bằng giải
thuật Sàng mang tên nhà toán học Hi Lạp Eratosthene. Từ vài nghìn năm trước,
Eratosthenes đã dạy như sau:
Baì giảng của Eratosthenes
|
|
||||
Nếu trò muốn liệt kê toàn bộ các số nguyên tố nằm trong
khoảng từ 1 đến N hãy làm như sau
1. Viết dãy số từ 1 đến N.
2. Xóa đi số 1 vì nó không phải là số
nguyên tố, cũng không phải là hợp số. Nó là một số đặc biệt.
3. Lần lượt duyệt từ 2 đến như sau.
Nếu gặp số chưa bị xóa thì đó chính là một số nguyên tố. Trò hãy xóa mọi bội
của số này kể từ bình phương của nó trở đi.
Khi kết thúc, những số nào không bị xóa
trên tấm bảng sẽ là các số nguyên tố. Đó là kho các số nguyên tố trong khoảng
1..N.
|
Thời đó chưa có giấy viết nên thày trò phải viết trên những
tấm bảng bằng đất sét vào lúc đất còn dẻo, các số bị xóa được đục thủng. Sau
khi phơi khô ta thu được những tấm bảng thủng lỗ chỗ như một cái sàng gạo.
Với mảng a[0..MN]
of byte đủ lớn, thí dụ, MN = 60.000 ta có thể ghi nhận các số nguyên tố nằm trong khoảng
1..MN. Ta qui ước a[i] = 0 thì i là số nguyên tố, a[i] = 1 ứng với số i bị dùi
thủng nên i không phải là số nguyên tố.
procedure Eratosthenes(n: longint);
var i,j: longint;
begin
fillchar(a,sizeof(a),0);
for i := 2 to
round(sqrt(n)) do
if a[i]=0 then
for j := i to (n div
i) do a[i*j] := 1;
end;
Thủ tục phân tích N!
ra thừa số nguyên tố dạng cải tiến sẽ như sau,
procedure NewFac(n: longint);
const bl = #32; { Dau cach }
var i,p: longint;
begin
Eratosthenes(n);
writeln;
for i := 2 to n do
if a[i] = 0 then
begin
p := Power(n,i);
if P > 0 then
writeln(i,bl,p);
end;
end;
Dùng kỹ thuật đánh dấu bit có thể tạo kho số nguyên tố cỡ
8.MN vì một byte có 8 bit, mỗi bit sẽ quản lí 1 số.
Mảng a vẫn được khai báo như trước: a[0..MN] of byte
(quan trọng là chỉ số phải tính từ 0 trở đi) nhưng lúc này mỗi phần tử a[i] sẽ
quản lí 8 số chứ không phải một số như trước. Tiếp đến bạn cần viết thêm ba thủ tục sau đây:
Thủ tục BitOn(i) - đặt trị 1 cho bit thứ i trong dãy bit a (bật
bit). Các bit trong dãy a sẽ được mã số từ 0 đến 8MN-1= 480.000-1. Bản thân số
480.000 là hợp số nên ta có thể bỏ qua.
procedure BitOn(i: longint);
var b,p: longint;
begin
b := i shr 3; { i div 8 }
p := i and 7; { i mod 8 }
a[b] := a[b] or (1 shl p);
end;
|
Đặt trị 1 cho bit i trong dãy bit a
1. Xác định xem bit i nằm
trong byte nào
b := i div 8
2. Xác định xem bit i là
bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8
3. Lấy số nhị phân 8 bit
00000001 dịch trái p vị trí rồi cộng logic theo bit với a[b].
a[b] := a[b] or (1 shl p);
|
Bạn ghi nhớ sự tương đương của các phép toán sau đây
Phép toán
|
Phép toán tương đương
|
x div 2k
|
x shr k
|
x mod 2k
|
x and 2k-1
|
Tính theo dạng này sẽ nhanh hơn
|
Thủ tục BitOff(i) đặt trị 0 cho bit thứ i
trong dãy bit a (tắt bit).
procedure BitOff(i:
longint);
var b,p: longint;
begin
b := i shr 3; { i div 8 }
p := i and 7; { i mod 8 }
a[b]:=a[b] and (not(1 shl p));
end;
|
Đặt trị 0 cho bit i trong dãy bit a
1. Xác định xem bit i nằm
trong byte nào
b := i div 8;
2. Xác định xem bit i là
bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8;
3. Lấy số nhị phân 6 bit
00000001 dịch trái p vị trí, lật rồi nhân logic theo bit với a[b].
a[b]:=a[b] and (not(1 shl p));
|
Hàm GetBit(i) cho ra trị (1/0) của bit
i trong dãy bit a.
function GetBit(i:
longint): byte;
var b,p: longint;
begin
b := i shr 3;
p := i and 7; { i mod 8 }
GetBit := (a[b] shr p) and 1;
end;
|
Đặt trị 0 cho bit i trong dãy bit a
1. Xác định xem bit i nằm
trong byte nào
b := i div 8;
2. Xác định xem bit i là
bit thứ mấy trong byte b (tính theo trật tự 7,6,5,4,3,2,1,0)
p := i mod 8;
3. Dịch a[b] qua phải p
vị trí, rồi nhân logic theo bit với 00000001 để lấy bit phải nhất (bit 0).
GetBit := (a[b] shr p) and 1;
|
Các thủ tục cơ bản theo kỹ thuật xử lí bit khi đó sẽ như
sau.
procedure Eratosthenes_B(n: longint);
var i,j: longint;
begin
fillchar(a,sizeof(a),0);
for i:=2 to
round(sqrt(n)) do
for j:=i to (n div i)
do
BitOn(i*j);
end;
procedure BFac(n: longint);
const bl = #32; { Dau cach }
var i,p: longint;
begin
Eratosthenes_B(n);
writeln;
for i:=2 to n do
if GetBit(i)=0 then
begin
p := Power(n,i);
if P > 0 then
writeln(i,bl,p);
end;
end;
Độ phức tạp
Để liệt kê các số nguyên tố từ 1..N ta duyệt từ 1 đến , với mỗi số nguyên tố ta phải gạch tối đa cỡ N các bội của
chúng. Vậy độ phức tạp tính toán cỡ N..
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét