Mình chưa hiểu lắm tại mình hơi dốt toán 
Về thuật toán phân tích thừa số nguyên tô
(tiếp theo) vậy thì vòng lặp tạm dừng ở i = p1 vì p1 là nhỏ nhất rồi. Quan sát kĩ vòng lặp thì ta thấy rằng điều kiện dừng chia là n mod i != 0 nên sau đó i > p1.
Nếu n_mới = 1 (hay n_cũ = p1^e1) thì thuật toán dừng và chạy đúng.
Ngược lại n_mới = p2^e2 * p3^e3 * ... và ta lại trở lại giả thiết ban đầu: số chia tiếp theo phải là p2, v.v…do i <= p2 < p3 < …
Thay vì đặt điều kiện vòng lặp là i<= sqrt(n) sao mình không để (n > 1) ?
đỡ phải tính sqrt.
thế cũng được, nhiều cách mà.
Nhưng mà nếu điều kiện là n thì cuối cùng sẽ in ra n* chứ không phải n như cách của mình. Có thể dùng while (i<n) thì không phải tính sqrt.
def t(n, i=2):
while (n > 1):
if (n%i != 0):
i += 1
else:
print (i)
n = int(n/i)
if n>1:
print('*')
sửa lại chút cho phù hợp là được
Ai cho mình cái link chỉ up code lên với, copy paste ko dc @@
Làm thế gặp số nguyên tố thì sẽ chạy từ 1 đến n nhé.
Nếu n là số nguyên tố thì cách đấy vẫn phải chạy từ 1 đến n thôi.
Hiểu, nhưng không biết complex của hai cách cái nào hơn cái nào, dù sao của sqrt cũng kha khá.
Mình nói leo phát cho bạn nào mới học lập trình: lưu sqrt(n) lại trong 1 biến nếu cần dùng nhiều lần để tiết kiệm, tránh phải tính đi tính lại 1 thứ tốn thời gian.
a = sqrt(n)
while (i<=a) do
…
n giảm dần mà, đâu phải tính đi tính lại đâu?
trường hợp xấu khi n là số nguyên tố hoặc chỉ chia hết cho 2, 3 và một số rất lớn thì while (i ≤ a) mới ít hơn while (i < n). Còn nếu như n kiểu như 100000000 thì cách while (i < n) lợi hơn.
1 Like
uh nhỉ, mà thôi kệ đi, core i5 i7 xá gì chút xíu complex cho nhức đầu, hực
Thế sao không tính một lần sqrt()? Có mất gì đâu.
(pseudocode)
: Input: n
: x := sqrt(n);
for i:=2 to x do
while(n mod i = 0) begin
n := n div i;
if n != 1 then print('*');
end;
3 Likes
Thì mình đề nghị ở post trước đó 
Trả lời cho câu hỏi của bạn:
Các số không phải là số nguyên tố đều có thể phân tích thành tích của các số nguyên tố nhỏ hơn có nghĩa là nếu n đã không chia hết cho các số nguyên tố trước đó thì sẽ không chia hết cho các số đứng sau.
VD n=14
vòng lặp 1: 14/2 =7
vòng lặp 2: 7/3 <>0
vòng lặp 3: 7/4 <>0 (n đã không chia hết cho 2, nên chắc chắn sẽ không chia hết cho 4)
vòng lặp 4: 7/5 <>0
vòng lặp 5: 7/6 <>0 (n đã không chia hết cho 2, nên chắc chắn sẽ không chia hết cho 6)
vòng lặp 6: 7/7 =1
Thuật toán bạn đưa ra không bỏ qua các số không phải là số nguyên tố mà do số ấy không phải là ước của n nên không được in ra.
Hope it help you
3 Likes
Bạn Gia Huy đã trả lời đúng câu hỏi của bạn rồi đấy. Khi bạn kiểm tra đến 1 số bất kỳ không phải số NT, thì nó chắc chắn sẽ không chia hết cho các số đấy, vì ước của số đấy nó cũng đã không chia hết rồi.
Còn về thuật toán thì chuẩn nhất rồi, không cần phải sqrt đâu. Vì số vòng lặp là số ước của nó nên ít hơn việc bạn đặt vòng lặp for từ 1 đến x=sqrt(n).
1 Like
Nếu n là số nguyên tố thì vẫn chạy từ 1 đến n đấy 
1 Like
Cách nhanh nhất ý, là “cache”.
Tức là liệt kê tất cả các số nguyên tố nhỏ hơn max của longint cho vào một file, coi như cái sàng, sau này có làm với số khác thì dùng cái đó :v
2 Likes
Thằng cu mới học Pascal mà đã thế thì chết à. 
Nói chung mức độ học cơ bản thì hiểu bản chất của vấn đề là ok rồi. Nếu đưa ra được các thuật toán tối ưu nhất thì càng OK.
1 Like
mình thử thôi 
i := 2;
while ( i ≤ sqrt(n)) do
if (n mod i = 0) then
begin
write(i,'*');
n := n div i;
end
else
i := i + 1;
write(n);
1 Like
Cảm ơn tất cả mọi người, giờ em hiêu rồi 
procedure ptngto(N:integer);
var i:integer;
Begin
i:=2;
while N<>1 do
Begin
if(N mod i=0) then
begin
write(i);
N:=trunc(N/i);
if(N>1) then
write('*');
end
else
i:=i+1;
End;
End;
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?