Về thuật toán phân tích thừa số nguyên tô

Vì nó chia cho cả lũy thừa của một số nguyên tố (power primes).
Mà nên sửa lại chạy tới sqrt thôi.

Giờ ta có n = p1^e1 * p2^e2 * ... sắp xếp theo chiều tăng của p[i].

Phần neo: Số đem chia đầu tiên luôn là một số nguyên tố vì hợp số phải chia hết cho một số nguyên tố nhỏ hơn, và áp dụng t/c bắc cầu.

Nhưng thế này vẫn chưa đủ để chứng minh tính đúng đắn. Thôi bạn thớt giải tiếp vậy.

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);

Mình chưa hiểu lắm tại mình hơi dốt toán

(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é.

Có thể dùng while (i<n) thì không phải tính sqrt.

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.

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), i := 2

for i:=2 to x do
   while(n mod i = 0) begin 
       n := n div i;
       if n != 1 then print('*');
   end;

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

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).

Nếu n là số nguyên tố thì vẫn chạy từ 1 đến n đấy

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

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.