Tối ưu chương trình phân tích thừa số nguyên tố

[honghm211 (hoan_h3)]

đề bài : phân tích thừa số thành tích các thừa số nguyên tố.

int main() {
    int n;
    scanf("%d", &n);
    int tmp = n;
    while(n%2==0) {
        printf("%d ", 2);
        n/=2;
    }
    while(n%3==0) {
        printf("%d ", 3);
        n/=3;
    }
    if(n>1) {
        int i=5, k=2;
        for(i; i<=sqrt(tmp); i+=k, k = 6 - k) {
            if(n<=1) break;
            while(n%i==0) {
                printf("%d ", i);
                n/=i;
            }
        }
        if(n>1) printf("%d ", n);
    }
    return 0;
}

mọi người giúp em tối ưu thuật được không ạ

[Reborn (David Martin)]

Bạn có thể dùng algorithm của Pollard’s Rho.

[rogp10]

Nếu n chia hết cho i thì bắt đầu vòng lặp chia, sau vòng lặp này gán lại tmp xuống luôn.

Dùng Rho/ECM thì chia thử một ít, thử nguyên tố rồi chạy Rho/ECM.

[honghm211 (hoan_h3)]

e thay tmp = n không cần gán tmp cũng đc rồi, nhưng đoạn sau là sao vậy ạ