Phân tích số nguyên dương thành tích các thừa số nguyên tố

cách nào để phân tích một số nguyên dương thành các thừa số nguyên tố với (2<=n< 2*10^9)
tất cả các bộ text đề chạy không quá 1 giây
 

tengiday

Happy life
Nếu chỉ phân tích một số thì đâu có gì chạy không quá 1 giây đâu. Bình thường bạn viết như thế nào?
 
[FONT=&quot]i:=2;[/FONT]
[FONT=&quot] REPEAT[/FONT]
[FONT=&quot] WHILE n MOD i <> 0 DO[/FONT]
[FONT=&quot] i:=i+1;[/FONT]
[FONT=&quot] Write(i);[/FONT]
[FONT=&quot] n:=n DIV i;[/FONT]
[FONT=&quot] IF n > 1 THEN[/FONT]
[FONT=&quot] write ('*');[/FONT]
[FONT=&quot] UNTIL n = 1;[/FONT]
 

tengiday

Happy life
Nếu chỉ phân tích 1 số thì đoạn code của bạn là đẹp rồi, ko thể nào chạy hơn 1 giây đc cả (trừ khi bạn chạy trên máy đời cổ; trong trường hợp đó thì thuật toán nào cũng vô dụng). Mình đã test thử bằng Pascal online rồi. Bạn thử thêm đoạn đo thời gian như sau:
Mã:
uses DateUtils, SysUtils;
var fromTime, toTime: TDateTime;
    milDiff : int64;

BEGIN.
    FromTime := Now;

    // đoạn code của bạn

    ToTime := Now;

    milDiff := MilliSecondsBetween(ToTime,FromTime);
    writeln(milDiff);
END.
 
nei xay dung ham so nto như thế này rooif thực hiện như trên theo bạn thế nào
Var Can,i:Longint;
Begin
If (K=2) or (K=3) then Begin NT:=True;Exit; End;
If (K<2) or (K mod 2 = 0) or (K mod 3 = 0) then
Begin NT:=False; Exit; End;
NT:=True;
i:=5;
Can:=Trunc(sqrt(K));
While i<=Can do
Begin
if (K mod i = 0) or (K mod (i+2) =0) then
Begin NT:=False; Exit; End
ELse inc(i,6);
End;
End;
với lại mình thấy code
i:=2;
REPEAT
WHILE n MOD i <> 0 DO
i:=i+1;
Write(i);
n:=n DIV i;
IF n > 1 THEN
write ('*');
UNTIL n = 1;
chạy vẫn lâu mà bạn
nếu nhập vào là số nguyên tố mà lớn vẫn lâu ma bạn vì vòng lặp mỗi lần chỉ tăng lên 1
 

tengiday

Happy life
Bên trong vòng 'while' bạn exit ra nếu i > sqrt(n). Như vậy sẽ cải thiên đc nhiều lắm.
Nếu thời gian đc tính ngay khi đọc đc n thì bạn làm nguyên tố không có ý nghĩa, bởi vì ngay vòng "while" bên trong đã là xét từng ước của n rồi.
 
hoc sinh minh di thi lo lam theo xay dung ham roi kiem tra. theo ban nhu the co diem ko ban. cau nay 3 diem ban oi moi bo khoang 05 diem .minh lo qua
 

tengiday

Happy life
hoc sinh minh di thi lo lam theo xay dung ham roi kiem tra. theo ban nhu the co diem ko ban. cau nay 3 diem ban oi moi bo khoang 05 diem .minh lo qua
Thực ra tính thời gian chưa hẳn là cách đánh giá thuật toán tốt vì nó phụ thuộc vào máy đang test. Nhiều ct không qua được thời gian với máy đời cũ thì nay lại qua được với máy đời mới.
 
var
n,i:longint;
begin
write('n=');
readln(n);
i:=2;
while i*i<=n do
begin
while n mod i=0 do
begin
write(i);
n:=n div i;
if n>1 then write(' ');
end;
if i=2 then i:=3 else i:=i+2;
end;
if n<>1 then write(n);
readln
end.
mÌNH THẤY CÁCH NÀY CHẠY RẤT NHANH NHƯNG THỰC SỰ KO HIỂU LẮM..
 
hình như theo phương pháp là vc theo bội số thì pải.. nếu a là snt thì bội aooa của a là hợp số
 
Top