Существует ли эффективный алгоритм для перечисления факторов рядаnв порядке возрастания, без сортировки? Под «эффективным» я имею в виду:

Алгоритм позволяет избежать грубого поиска делителей, начиная с факторизации простой степениn.

Сложность алгоритма во время выполнения равна O (d log₂d) или лучше, гдеd это число делителейn.

Пространственная сложность алгоритма составляет O (d).

Алгоритм избегает операции сортировки. То есть факторы производятсяс целью а не произведено из заказа и отсортировано позже. Хотя перечисление с использованием простого рекурсивного подхода, а затем сортировка - это O (d log₂d), существует очень ужасная стоимость всех обращений к памяти, связанных с сортировкой.

Тривиальный примерn = 360 = 2³ × 3² × 5, который имеетd= 24 фактора: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 , 360}.

Более серьезный примерn = 278282512406132373381723386382308832000 = 2⁸ × 3⁴ × 5³ × 7² × 11² × 13² × 17 × 19 × 23 × 29 × 31 × 37 × 41 × 43 × 47 × 53 × 59 × 61 × 67 × 71 × 73 × 79, что имеетd= 318504960 факторов (очевидно, их слишком много, чтобы перечислять здесь!). Это число, между прочим, имеет наибольшее количество факторов из любого числа до 2 ^ 128.

Я мог поклясться, что видел описание такого алгоритма несколько недель назад с примером кода, но сейчас я не могу его найти нигде. Он использовал некоторый фокус для поддержания списка индексов прародителей в выходном списке для каждого простого фактора. (Обновление: я путал генерацию факторов с числами Хэмминга, которые работают аналогично.)

Обновить

Я закончил, используя решение, которое является O (d) во время выполнения, имеет чрезвычайно низкую нагрузку на память, создавая O (d) вывод на месте, и это значительно быстрее, чем любой другой метод, который я знаю. Я отправил это решение как ответ, с исходным кодом на языке C. Это сильно оптимизированная, упрощенная версия прекрасного алгоритма, представленная здесь в Haskell другим участником, Уиллом Нессом. Я выбрал ответ Уилла в качестве принятого ответа, поскольку он предоставил очень элегантное решение, которое соответствовало всем требованиям, как было заявлено изначально.