Ответ 1
Руководство Gnu coreutils сообщает, что используется алгоритм Полларда rho.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
команда коэффициента печатает основные факторы указанного целого числа NUMBER.
когда я попробовал его
factor 12345678912345678912
даже для таких больших чисел, это происходит в мельницах.
, какой алгоритм использует?
Руководство Gnu coreutils сообщает, что используется алгоритм Полларда rho.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html
Здесь приведен пример одной версии источника для коэффициента GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Он включает подпрограммы как для пробного деления, так и для Полларда rho. Похоже на быстрый просмотр, как если бы он использовал пробное деление, чтобы найти некоторые небольшие факторы (примерно до lg(n)^2
, что в этом случае составляет около 4000), а затем Поллард, если то, что осталось, не является, вероятно, простым. В этом случае 205432623008947
, если я прав около 4000, т.е. 35129 * 5847949643
.
Второй по величине простой коэффициент в вашем примере - 35129
, а квадратный корень самого большого - около 76471
. Таким образом, одно только пробное деление было бы быстрым, так как ему нужно было попробовать только около 25 тысяч кандидатов.