Каков алгоритм, лежащий в основе команды factor в linux?

команда коэффициента печатает основные факторы указанного целого числа NUMBER.

когда я попробовал его

factor 12345678912345678912

даже для таких больших чисел, это происходит в мельницах.

, какой алгоритм использует?

Ответы

Ответ 2

Здесь приведен пример одной версии источника для коэффициента GNU:

http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c

Он включает подпрограммы как для пробного деления, так и для Полларда rho. Похоже на быстрый просмотр, как если бы он использовал пробное деление, чтобы найти некоторые небольшие факторы (примерно до lg(n)^2, что в этом случае составляет около 4000), а затем Поллард, если то, что осталось, не является, вероятно, простым. В этом случае 205432623008947, если я прав около 4000, т.е. 35129 * 5847949643.

Второй по величине простой коэффициент в вашем примере - 35129, а квадратный корень самого большого - около 76471. Таким образом, одно только пробное деление было бы быстрым, так как ему нужно было попробовать только около 25 тысяч кандидатов.