Для нахождения канонического разложения целых
Резюме
Для нахождения канонического разложения целых чисел, дробей и целых гауссовых чисел лучше всего подходит функция Factor-Integer. Она возвращает список пар простых делителей и их показателей, а также, при необходимости, делитель единицы, указывающий знак или позволяющий сгруппировать сопряженные множители. При этом сорока-, а то и шестидесятиразрядные числа разлагаются практически сразу. Среди же семидесяти- и восьмидесятиразрядных чисел велика вероятность встретить число, (растеризовать которое за приемлемое время не удается. (Двоичное представление таких чисел содержит более двух сотен цифр.) Во всяком случае, не стоит пытаться делать это в цикле, если в нем не предусмотрены какие-либо средства оповещения о ходе выполнения процесса факторизации. Конечно, в отдельных случаях могут быть успешно разложены и числа, десятичная запись которых содержит и несколько десятков тысяч цифр. Обычно это степени или произведения степеней относительно небольших простых чисел. К этой категории можно отнести, например, факториалы.
Если же функция FactorInteger со своей работой за приемлемое время не справляется, можно сначала найти только те делители, нахождение которых не составит труда для нее, — именно для этого предназначена опция FactorComplete->False. Все же чаще приходится прибегать к имеющейся в пакете теории чисел функции FactorIntegerECM. Однако эта функция за один раз находит только один делитель, притом не обязательно простой. Кроме того, она может зациклиться, если в качестве аргумента получит простое число. Так что перед вызовом этой функции нужно проверить, не является ли ее аргумент простым числом — это делается с помощью функции PrimeQ. (Как правило, функция PrimeQ работает очень быстро.) Получив очередной делитель, число можно разделить на него и проверить, не является ли частное простым числом. Если частное окажется простым числом, то фактически каноническое разложение можно считать полученным, если известны канонические разложения найденных ранее делителей. Если же частное или какой-нибудь делитель окажется числом составным, к нему можно попытаться снова применить функцию FactorIntegerECM. Повторяя эту процедуру достаточное число раз, иногда (для относительно небольших великанов часто) удается найти каноническое разложение.
Если же и этот метод не приводит к успеху, помочь могут различные формулы (например, разложения суммы или разности степеней и т.п.) и предварительно составленные таблицы. Благодаря системе Mathematica к таблицам приходится прибегать существенно реже, чем в докомпьютерную эпоху. Более того, сами таблицы можно составить с помощью программ, написанных на языке программирования, встроенном в систему Mathematica. Однако, как и в эпоху Эйлера и Гаусса, таблицы незаменимы при поиске нетривиальных закономерностей в канонических разложениях чисел того или иного вида. Однако представление, возвращаемое функцией Factorlnteger, несколько "однолинейно" и потому удобно скорее для дальнейшего использования в качестве аргумента других функций, чем для чтения человеком. Хотя это представление система Mathematica может преобразовать в различные форматы, подчас проще написать макрос, преобразующий его в привычный вид.