Bài toán phân tích một số n ra thừa số nguyên tố có thể chạy được với
n<=10^12.
Có một số bạn làm quá thừa khi phải mất công kiểm tra 1 số có phải là số nguyên tố không,vừa tốn bộ nhớ vừa tốn thời gian chạy mà chả giải quyết cái gì .Khi một số n mà phân tích ở dạng p^k.A với p nguyên tố và k là lớn nhất,thì chắc chắn rằng A sẽ không chia hết cho p nữa,điều đó có nghĩa là nếu A không chia hết cho p thì mọi bội số của p A cũng sẽ không chia hết => chả việc gì phải kiểm tra số nguyên tố cho mất thời gian
Ta có nhận xét chỉ có số 2 là số nguyên tố chẵn,đầu tiên ta phân tích n = 2^t.q
Code:
while not odd(n) do
begin
inc(top);
a[top]:=2;
n:=n div 2;
end;
Sau đó mình sẽ dùng một biến i để tính tiếp
Code:
i:=3;
while (i<=trunc(sqrt(n))+1) do
begin
while (n mod i=0) do
begin
inc(top);a[top]:=i;
n:=n div i;
end;
i:=i+2;
end;
if n>1 then
begin
inc(top);
a[top]:=n;
end;
Sau vòng lặp nếu n>1 => chắc chắn n là số nguyên tố => add thẳng vào mảng a.
Mảng a chính là mảng kết quả.
Độ phức tạp trong TH xấu nhất là O(sqrt(n)).
Bạn nào vẫn còn phân vân việc có phải kiểm tra nguyên tố hay không thì cứ cóp code vào chạy thử rồi sẽ nhận ra tại sao lại vậy
[=========> Bổ sung bài viết <=========]
Được gửi bởi
xbach17
uses crt;
var n,i,j,dem,mu:longint;
begin
clrscr;
write('nhap n:');readln(n);
write(n,'=');
for i:=2 to n-1 do
begin
if (n mod i=0) then
begin
for j:=2 to i do
begin
if i mod j=0 then break;
end;
if j=i then
begin
dem:=0;mu:=1;
repeat
mu:=mu*i;
dem:=dem+1;
until n mod mu<>0;
write(i,'^',dem-1,'*');
end;
end;
end;
readln;
end.
BÀi giải đây!
Không những dài mà còn không chạy được với n cỡ 10^8 .Cái này mình ko nhầm độ phức tạp còn > O(N)
Bookmarks