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

Арифметика: разложение целых чисел на простые множители

• Факторизация целых чисел с помощью функции FactorInteger. Факторизация чисел Мерсенна.

  В ряде задач очень важно знать, насколько быстро можно разложить целое число на простые множители. По этой причине давайте рассмотрим, какие числа функция FactorInteger может разложить на простые множители за приемлемое время.

• Факторизация чисел Ферма

  Факторизация чисел вида 2n+1 | Среди чисел вида 2n +1 простые, можно сказать, почти не встречаются, ведь число такого вида может быть простым только тогда, когда n является степенью двойки: n = 2*. Такие числа называются числами Ферма: | Fn = 22n +1. | Пьер Ферма утверждал, что все такие числа просты.

• Факторизация чисел, десятичная запись которых состоит из n единиц

  До сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2n. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна Mn, например, записывается n единицами, а число 2n +1 – двумя единицами, между которыми стоит n-1 нуль (рассматриваем случай n > 0).

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

  Факторизация чисел вида 10n+1 | Теперь, следуя логике изучения чисел, близких к 2n, построим таблицу факторизации чисел вида 10n +1. В десятичной системе счисления запись таких чисел начинается и заканчивается единицей, а между этими единицами стоят нули: | 10n + 1 = 1000……………………….00001 (n-1 нулей).

• Факторизация дробей

  Прочитав заголовок, вы, возможно, скажете: "Раскладывать дроби на простые множители? Да как же это?! Такой операции в арифметике нет!". Действительно, такой операции вроде бы и нет, но вспомните, как часто приходится раскладывать на простые множители числитель и знаменатель одной и той же дроби.

• Факторизация гауссовых чисел

  Напомним, что гауссовыми называются комплексные числа, у которых действительная и мнимая части являются целыми числами. Иными словами, это комплексные числа а+bi, у которых вещественная (а) и мнимая (b) части представляют собой целые числа.

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

  Как мы уже видели, функция Factorlnteger вполне справляется с разложением чисел, десятичная запись которых содержит не более 60-70 десятичных знаков (это примерно две сотни двоичных). Хотя именно такие числа чаще всего встречаются на практике, их множество конечно.

• Функция FactorIntegerECM (попытка факторизации больших чисел Мерсенна)

  Давайте на примере попытки разложения больших чисел Мерсенна рассмотрим, к ак Mathematica позволяет приблизиться к решению задачи факторизации очень больших чисел. | Факторизация 317-го числа Мерсенна М317 | Конечно, можно попытаться применить функцию Factorlnteger.

• Резюме

  Для нахождения канонического разложения целых чисел, дробей и целых гауссовых чисел лучше всего подходит функция Factor-Integer. Она возвращает список пар простых делителей и их показателей, а также, при необходимости, делитель единицы, указывающий знак или позволяющий сгруппировать сопряженные множители. При этом сорока-, а то и шестидесятиразрядные числа разлагаются практически сразу.