Иллюстрированный самоучитель по Mathematica 5

Факторизация очень больших чисел

Обычно пятикласснику (участнику городской или районной олимпиады по математике) нужно от пяти до десяти минут на вывод и проверку необходимой формулы. Но ведь Mathematica (точнее, функция FactorInteger) не проверяет, является ли каждое предлагаемое ей число факториалом некоторого другого числа, и потому применить формулу не сможет! Так сколько же ей понадобится времени на факторизацию этого монстра? На самом деле ответ получается в мгновение ока.

Почему же тогда это разложение получается так быстро? Тому есть две причины. Во-первых, функция Factorlnteger реализует довольно хитрый алгоритм (и к тому же усовершенствованный в версии 5), который умеет пользоваться особенностями числа и ранее найденными множителями. Во-вторых, число имеет малые простые делители, притом в достаточно больших степенях (взгляните на разложение и убедитесь в этом самостоятельно). Поэтому уже в самом начале, как только найден очередной небольшой простой делитель, число делится на его достаточно большую степень, и поиск следующего делителя выполняется для уже значительно меньшего числа. Например, когда найдены все простые делители, меньшие 500, остается факторизовать число:

А ведь это число существенно меньше первоначального. К тому же его простые делители также являются последовательными простыми числами. И потому, хотя уже и не так стремительно, но подлежащее факторизации число все время уменьшается. А это значит, что не приходится испытывать числа, большие 1000. Добавьте сюда еще одну техническую деталь: работать приходится с все более короткими числами, и вы поймете, почему процесс заканчивается столь быстро.

Но есть огромное множество гораздо меньших чисел (вроде 1001-1, (10⁷⁹ -1)/9 и т.д.), которым повезло гораздо меньше. Быстро разложить их функция Factorlnteger не может. Как же быть?