lệnh hệ số in các yếu tố chính của số nguyên được chỉ định NUMBER.Thuật toán đằng sau lệnh hệ số trong linux là gì?
khi tôi đã cố gắng nó
factor 12345678912345678912
ngay cả đối với số lượng lớn như vậy, nó kết quả trong các nhà máy.
thuật toán nào được sử dụng?
Hướng dẫn sử dụng lõi hạt nhân Gnu thông báo rằng Pollard's rho algorithm đang được sử dụng.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
Dưới đây là một ví dụ về một phiên bản của nguồn cho yếu tố GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Nó bao gồm thói quen cho cả bộ phận dùng thử và rho Pollard của. Hình như tôi sử dụng phép quét nhanh như thể sử dụng phân chia thử nghiệm để tìm một số yếu tố nhỏ (lên đến khoảng lg(n)^2, khoảng 4000 trong trường hợp này), sau đó Pollard nếu những gì còn lại không phải là nguyên tố. Trong trường hợp này là 205432623008947 nếu tôi đúng về 4000, tức là 35129 * 5847949643.
Yếu tố chính lớn thứ hai trong ví dụ của bạn là 35129 và căn bậc hai lớn nhất là khoảng 76471. Vì vậy, phân chia thử nghiệm một mình sẽ nhanh chóng, vì nó chỉ phải thử khoảng 25 nghìn ứng cử viên.