Теория чисел
Прайм-факторизация в Python: часть 1
Узнайте, как написать программу на Python для разложения числа на простые множители!
Существует множество подходов к простой факторизации, но какой из них лучше? Я знаю, что лучшая — это субъективный термин, но когда я говорю «лучшая», я говорю о программе, которая сочетает в себе эффективность и меньше кода.
Подход
Давайте сначала поговорим о том, как мы будем подходить к решению этой проблемы. Самый простой способ — использовать Python для создания списка простых чисел, а затем проверить число на соответствие каждому из простых чисел в этом списке.
Однако, если мы просто создадим кучу циклов, процесс займет много времени. Нам понадобится использовать математический алгоритм.
Большинство из вас, если вы когда-либо углублялись в мир математики, должны были слышать о решете Эратосфена. Это сито — простой способ генерировать большое количество простых чисел, однако для эффективного использования его необходимо оптимизировать. Первая часть решения будет направлена на решение этой проблемы.
После создания достаточно большого списка простых чисел нам нужно будет проверить каждое из них на число. Это можно сделать довольно быстро для любого большого числа: всего около 10 000 простых чисел меньше 1 миллиона, и не стоит недооценивать мощность компьютера.
Подход состоит в том, чтобы использовать решето Эратосфена для создания списка простых чисел, а затем использовать этот список для вынесения простых чисел из заданного числа.
Оптимизация решета Эратосфена
Хорошо, приступим. Вот краткий обзор того, что делает Решето Эратосфена:
В математике решето Эратосфена — это древний алгоритм нахождения всех простых чисел до любого заданного предела.
Он делает это путем итеративной маркировки как составных (т. е. не простых) кратных каждому простому числу, начиная с первого простого числа, 2. Кратные числа данного простого числа генерируются как последовательность чисел, начиная с этого простого числа, с постоянная разница между ними, равная этому простому числу.
Это довольно многословно (как и большинство текстов, цитируемых из Википедии), но вот процесс, упрощенный в несколько простых шагов:
- Начните со списка целых чисел, начиная с 2 до некоторого предела
- Пусть p = 2, тогда вычеркнем из списка все числа, кратные 2, кроме 2
- Затем установите p равным следующему не отмеченному числу в списке и отметьте все числа, кратные этому p.
- Повторяйте это до тех пор, пока не останется возможного значения p.
Конечно, нам придется немного оптимизировать это, прежде чем мы добьемся, чтобы оно стало достаточно эффективным для больших чисел.
Шаг 1
Вместо того, чтобы начинать со списка целых чисел, мы инициализируем список логических значений до нашего предела: в конце, если sieve[i-1] равно True , то i является простым числом; в противном случае он составной.
Здесь мы определили функцию с именем eratosthenes , инициализировали пустой список, называемый простыми числами (который мы будем использовать для хранения наших простых чисел позже), установили наш предел как входной параметр n и, наконец, инициализировали список True логических значений до limit + 1. .
Шаг 2–4
Теперь мы можем позаботиться об остальных шагах. Как следует из шага 2, нам нужно начать с 2, а затем пометить все числа, кратные 2, кроме 2, как False . Код ниже делает именно это:
Здесь я установил a = 2 , а затем увеличил a на 1 каждый раз, когда цикл завершается. Таким образом, хотя квадрат a меньше предела, мы помечаем все числа, кратные 2, как False, как показывает код. Когда квадрат a превышает предел, цикл останавливается, и у нас есть все необходимые простые числа.
Однако простые числа по-прежнему имеют форму логических значений: True или False. Следовательно, что мы должны сделать, так это для каждого значения в списке sieve мы должны проверить, является ли оно True или False . Если это True , то это означает, что число простое, поэтому мы добавляем его в наш список primes . Если это False , мы пропускаем.
Теперь, когда мы оптимизировали и разработали функцию для генерации простых чисел, теперь мы должны проверить эти простые числа на соответствие нашему числу для факторизации.
Факторизация числа
Вот более простая часть! Что нам нужно сделать, так это проверить каждое простое число на делимость в нашем числе. Сначала мы устанавливаем простые числа равными простым числам, сгенерированным нашей предыдущей функцией eratosthenes, затем инициализируем пустой список с именем factors.
Вот немного более сложная часть. У нас есть цикл for, встроенный в цикл while. Я подробно объясню каждую часть ниже:
Начнем с цикла for. По сути, он сообщает компьютеру, что для каждого значения в списке простых чисел необходимо проверить, равен ли x модуль i 0: другими словами, компьютер проверяет, делится ли каждое значение в i на x.
Затем, когда он находит фактор, он добавляет его в список factors. Затем он устанавливает x равным x / i (мы не хотим считать один и тот же множитель несколько раз), а затем break зацикливается.
Но мы хотим начать этот процесс заново для нового значения, которое мы установили для x. Вот тут-то и появляется цикл while: он гарантирует, что компьютер сделает это несколько раз для всех x, пока x не станет 1, что означает, что мы исчерпали все возможные простые числа и пришли к ответу.
Окончательный код и заключение
В двух предыдущих разделах я объяснил, как получить две функции в Python: eratosthenes, используемую для создания списка простых чисел, и factorize, используемую для использования этого списка простых чисел для получения списка факторов. Вот окончательный код:
Вот небольшая серия вещей, которые вы можете проверить:
- Попробуйте разложить на множители 20, 40 и 78, запустив
factorize(20),factorize(40)иfactorize(78). - Попробуйте разложить 1 000 304 на множители с помощью
factorize(1000304). Намного быстрее, чем вы думали? Однозначно быстрее, чем вручную!
Я говорил об эффективности в начале этой статьи. Я думаю, что это настолько просто, насколько это возможно, при этом получая довольно хорошую эффективность. Однако разложение 1 000 304 на множители за 4 секунды может оказаться медленным.
Существует еще один алгоритм, известный как Pollard's Rho Algorithm , который при полной оптимизации занимает менее одной секунды (да, менее 1 секунды), чтобы найти множитель числа, состоящего из 100 цифр! Вы можете узнать больше об этом алгоритме в части 2:
Иди проверь это. А пока берегите себя и удачного кодирования!
