Эффективный алгоритм простой факторизации со списком простых чисел

Question

Я пытаюсь реализовать эффективный алгоритм, который может найти простую факторизацию для данного числа n. У меня также есть список всех простых чисел, по крайней мере, до n.

Например: если у меня число n = 50, результат должен быть: 2, 5, 5.

Мои идеи до сих пор:

1. Проверьте, если n == 1, если true вернет 1
2. Проверьте, если n == 2, если true вернет 2

Если оба 1. и 2. неверны:

Разделите n на 2 как можно чаще и добавьте 2 к вектору результатов Попробуйте найти (возможно, на 2) n в списке простых чисел. Если n находится в списке, добавьте его к результатам и верните результаты. Найдите наибольшее простое число в списке, которое меньше n. Разделите на простое число, найденное в Шаг 6. Если деление без остатка возможно, добавьте простое число к результатам. Проверьте, если n == 1, и верните результат, если оно истинно Повторите шаги 5-9.

Этот алгоритм эффективен или у вас есть идеи по улучшению?

Answer 1

Ваш предложенный алгоритм неэффективен. Вы должны делить не на наибольшее оставшееся простое число, а на наименьшее. И если наименьший квадрат больше, чем то, что осталось, то то, что осталось, является простым.

Ваш существующий алгоритм будет нуждаться в среднем в O(n/log(n)) делениях. Мое улучшение делает это O(sqrt(n)/log(n)) вместо этого. Что до сих пор не особенно эффективный алгоритм факторизации. Но это хорошо для нескольких миллионов.