Эффективно генерировать все составные числа меньше N (с их факторизацией)
Я хотел бы построить эффективный итератор/генератор Python, который дает:
- все составные числа меньше N
- Наряду с их простой факторизацией
я назову это «составными_с_факторами()»
Предположим, что у нас уже есть список простых чисел меньше чем N, или генератор простых чисел, который может сделать то же самое.
Заметьте, что мне:
- НЕ НУЖНО, чтобы числа выдавались в числовом порядке
- НЕ ВАЖНО, выдается ли 1 в начале или нет
- НЕ ВАЖНО, выдаются ли также простые числа
Я полагаю, что это можно сделать с помощью умного рекурсивного генератора...
Так, например, вызов композитов_с_факторами(16)может дать:
# yields values in form of "composite_value, (factor_tuple)"
2, (2)
4, (2, 2)
8, (2, 2, 2)
6, (2, 3)
12, (2, 2, 3)
10, (2, 5)
14, (2, 7)
3, (3)
9, (3, 3)
15, (3, 5)
5, (5)
7, (7)
11, (11)
13, (13)
Как видите исходя из порядка моего вывода, я понимаю эту работу, начав с наименьшего простого числа в доступном генераторе простых чисел и выведя все степени этого простого числа меньше N, а затем повторив попытку через степени этого простого числа, но на каждом этапе проверяя, если Я могу применять степени дополнительных простых чисел (и все равно быть меньше N). Когда все комбинации с ЭТИМ простым числом выполнены, отбросьте его и повторите со следующим наименьшим простым числом, доступным в генераторе простых чисел.
Мои попытки сделать это с помощью "рекурсивных генераторов" привели меня в замешательство относительно того, когда следует выйти из рекурсии с помощью "yield", или "поднять StopIteration", или "return", или просто выпасть из рекурсивной функции..
Спасибо за мудрость!
ДОПОЛНИТЕЛЬНОЕ ПРИМЕЧАНИЕ:
У меня есть один способ сделать это сейчас:Я написал функцию для разложения чисел на множители, так что я могу разложить их на простые числа и получить результаты. Без проблем.Я держу это невероятно быстро, полагаясь на кеш «что является наименьшим простым делителем числа N»… для N до 10 миллионов.
Однако, как только я выйду из кеша, мы перейдем к «наивному» факторингу. (Фу.)
Смысл этого поста в том,:
- что я предполагаю, что "создание больших композитов из их факторов" будет быстрее, чем "разложение больших композитов на множители"... тем более, что меня НЕ волнует порядок, и
- Как сделать так, чтобы генератор Python "рекурсивно" вызывал сам себя и выдавал единый поток сгенерированных вещей?