Xin trợ giúp bài phân tích một số nguyên N <= 10^10 về thừa số nguyên tố luỹ thừa.
N = p1^x1 . p2^x2 . ..., trong đó pi là số nguyên tố phân biệt, còn xi là luỹ thừa tương ứng với pi.
Ví dụ: N = 12 = 2^2 . 3^1
Hiện tại mình chỉ biết tìm trong O(N), như thế thì chậm, mong các bạn gợi ý giúp cách tìm nhanh hơn.
Cảm ơn nhiều.
Độ phức tạp \(O([\sqrt{N}])\)
Duyệt \(i\) từ \(2\) đến \([\sqrt{N}]\)
: Làm như thuật \(O(N)\) của bạn, nếu \(N=1\) rồi thì break.
Nếu \(N \ne 1\) thì \(N\) là số nguyên tố, in ra \(N=N\)
Chứng minh tính đúng đắn như thuật toán kiểm tra một số có phải số nguyên tố hay không.
Như Bvl đã nói, bạn có thể duyệt đến \(\sqrt{N}\) để tìm ước số, nếu không tìm được thì N là số nguyên tố. Nếu N cỡ 10^10 thì phương pháp này có lẽ chạy ổn. Thông thường, bạn có thể thực hiên nhanh hơn \(\sqrt{N}\) nếu bạn biết kết hợp thuật toán kiểm tra tính nguyên tố Miller-Rabin. Xem chi tiết tại đây. Ở đây mình chỉ muốn bổ sung thêm một chút nếu bạn muốn phân tích với N lớn hơn . Với N lớn hơn (ví dụ cỡ 10^20) thì bạn có thể sử dụng thuật toán Pollard-Rho với độ phức tạp cỡ \(\sqrt[4]{N}\). Về phân tích thành nhân tử và kiểm tra tính nguyên tố, một vài bài viết ở đây có lẽ sẽ có ích:
Thuật toán Miller-Rabin kiểm tra tính nguyên tố. Thuật toán này có thể kiểm tra tính nguyên tố với N cỡ 10^50. Thuật toán Pollard-Rho phân tích thành nhân tử
