Основная теорема арифметики утверждает, что каждое положительное целое число (кроме числа 1) может быть представлено точно одним способом, за исключением перестановки, как произведение одного или нескольких простых чисел.
- Харди и Райт, «Введение в теорию чисел»
Простые числа - мощные и громоздкие вещи, и, независимо от того, любимы они или ненавидимы, они требуют нашего уважения. Они являются основой арифметики, стержнем криптографии и, возможно, языком первого контакта с разумной внеземной жизнью.
Поскольку даже краткий экскурс в теорию чисел покажет трудности, с которыми простые числа столкнулись даже с самыми блестящими математическими умами, это сообщение в блоге просто отдает дань уважения гигантам, на плечах которых мы стоим. Задача 3 проекта Эйлер - это возможность применить на практике концепцию, которую мы все усвоили в третьем классе, но, вероятно, не осознали до конца, пока не изучили набор простых чисел всесторонне: факторизация.
Прежде всего, определение простоты может быть выполнено с помощью одной из двух стратегий: проверки или доказательства. В компьютерной программе определение простоты путем тестирования почти всегда используется, поскольку оно является наиболее общим, но, следовательно, неэффективным. Чтобы облегчить это, компьютерные ученые делят тесты на простоту на десятки подтипов, которые быстрее дают ответы на определенные специализированные подмножества набора простых чисел. Другими словами, тестирование первичности - это огромная область математики и информатики, которая выходит далеко за рамки этого сообщения в блоге, которое, опять же, ограничено более скромной целью - простой факторизацией. Поэтому работу по тестированию на простоту следует рассматривать отдельно, и здесь она рассматривается только стандартным и поверхностным образом с использованием метода Ruby .prime?. »Для облегчения тестирования.
Во-первых, давайте рассмотрим два метода, которые находят наибольший простой множитель без использования факторизации.
Решение грубой силы
Этот метод грубой силы проверяет, является ли каждое число одновременно множителем и простым числом. Следовательно, первый будет самым большим простым фактором.
def largest_prime_factor_brute_force (number)
(3..Math.sqrt(number).to_i).to_a.reverse.each do |num|
if number % num == 0 && num.prime?
return num
end
end
end
Решение Flatiron
Это решение, предлагаемое Flatiron, исчерпывает все числа, которые одновременно являются факторными и простыми, но только явно проверяет, что они являются факторными. Тест на простоту неявно встроен в совместное присвоение деления, потому что по определению простые числа являются только самоделящимися. Таким образом, последний такой основной фактор будет самым большим.
def largest_prime_factor_flatiron(input)
prime = input
(2..Math.sqrt(input).to_i).each do |i|
break if prime <= 1
prime /= i while (prime > i && prime % i == 0)
end
prime
end
Решение факторизации
Объяснить факторизацию на примерах намного проще и быстрее. Помните: факторизация любого целого числа на простые множители уникальна. Практически каждый делал это раньше. Это простое разложение 29250:
29250 == 2 * (3 * 3) * (5 * 5 * 5) * 13 #=> "true story!"
Когда факторизация выполняется вручную, обычно используется дерево. Проблема в том, что существует множество видов деревьев, которые потенциально могут быть пройдены до достижения простой факторизации. Вот два способа разложить 29250 на простые множители:
Второе дерево, вероятно, более естественно при работе вручную, но оно очень глубокое, что означает более линейные вычисления; Кроме того, он очень узкий, что означает, что он должен проходить без особого преимущества параллельной обработки, которую с радостью предлагают нам продвинутые итераторы, такие как collect в Ruby. Следовательно, при разработке функции для разложения числа на его простые множители мы должны держать дерево широким и неглубоким, сначала находя наибольшие, а не наименьшие делители.
def prime_decomposition (factors)
factors.collect do |factor|
if factor == 1 || factor.prime?
factor
else
divisor = 2
until factor % divisor == 0 do
divisor += 1
end
dividend = factor / divisor
prime_decomposition([divisor, dividend])
end
end
end
Эта функция является рекурсивной, потому что план нахождения наибольшего делителя приводит к тому, что мы сначала не беспокоимся о его простоте; так как мы не знаем, достигли ли мы дна, мы должны продолжать рекурсивно повторять итерацию, пока не достигнем базового случая: простоты. Возможно, вы также заметили, что использование итератора сбора, хотя и эффективно, требует ввода массива и приводит к выходу потенциально вложенного массива. Это само по себе имеет два последствия. Во-первых, массив должен быть сглажен:
def prime_factors (natural_number) prime_decomposition([natural_number]).flatten end
Справедливо задаться вопросом, является ли вложение, а затем сглаживание неэффективностью, которую нужно реорганизовать. В данном случае это не так, поскольку стоимость сглаживания на каждом шаге рекурсии неизвестной, но потенциально большой глубины выше, чем использование высокооптимизированного и специально созданного метода сглаживания, такого как тот, который дал нам Ruby. Однако, конечно, будет такая глубина стека, при которой память будет переполняться, и встроенного выравнивания не избежать. Это приводит нас ко второму следствию вложенности, заключающемуся в том, что оно сохраняет структуру дерева, которая приводит к факторизации простых чисел, что означает, что дерево может быть реконструировано при желании. Однако проблема требовала наибольшего простого множителя, а не всех. Решим сейчас:
def largest_prime_factor(input) prime_factors(input).max end
Больше не должно быть парадоксальным, что нахождение максимума набора всех простых множителей путем первого разложения данного числа может быть более эффективным, чем попытка найти наибольший простой множитель напрямую или путем исчерпания. Ключ кроется в разработке алгоритма, который проходит по дереву факторизации простых чисел. По дереву нужно обходиться широко, чтобы оно оставалось как можно более мелким, чтобы использовать возможности параллельных вычислений итераций (vis a vis collect), чтобы разбить проблему на небольшие, управляемые и быстро решаемые части - другими словами: разделяй и властвуй.
Несколько заключительных мыслей: это не гонка. На мой взгляд, метод факторизации лучше всего ценится в том смысле, что он использует простую математику, с которой большинство из нас знакомо, и дает возможность применять важные концепции информатики, такие как рекурсия и уплощение. Однако важно убедиться, что наши методы не только красивы, но и практичны. Вот некоторые результаты тестов.
largest_prime_factor_brute_force: 0.150000 ( 0.154819) largest_prime_factor_flatiron: 0.050000 ( 0.053146) largest_prime_factor: 0.000000 ( 0.000240)
Метод грубой силы в 3 раза медленнее, чем метод утюга, а метод утюга в 221 раз медленнее, чем метод факторизации. Это делает метод грубой силы примерно в 650 раз медленнее, чем метод факторизации.
Опять же, все это следует воспринимать с недоверием. В зависимости от типа простого числа и диапазона рассматриваемых простых чисел некоторые методы, особенно очень продвинутые и специализированные, не рассматриваемые здесь, или даже самые простые, будут иметь очень специфические режимы оптимальности. Самый полезный вывод заключается не в том, какой из них является «лучшим», а в том, что у каждого из них есть сильные и слабые стороны, которые следует оценивать и использовать при необходимости.
