https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1333
cho mình hỏi bài này. số kiểu long long int. rất lớn . mà muốn phân tích thành tích các số nguyên tố thì có thuật toán gì sử dụng được không ạ?
giả sử n là một số nguyên tố có 19 chữ số. :((
mong mọi người giúp đỡ!
Theo mình nghĩ thuật toán Rho của Pollard (wikipedia: https://en.wikipedia.org/wiki/Pollard's_rho_algorithm, tiếng việt: http://www.giaithuatlaptrinh.com/?p=393) với độ phức tạp trung bình cỡ \(O(\sqrt[4]N)\)có thể factor được số cỡ 19 chữ số. Thuật toán khác tốt hơn bạn có thể thử là sàng bậc hai (quadratic sieve ). Sàng bậc hai là thuật toán khá hay nhưng mình không tìm được tài liệu tiếng Việt.
