Я бы хотел создать эффективный итератор/генератор Python, который дает:
- Все составные числа меньше N
- Наряду с их простой факторизацией
Я назову его "composites_with_factors()"
Предположим, что у нас уже есть список простых чисел, меньших N, или генератор простых чисел, который может сделать то же самое.
Обратите внимание, что I:
- НЕ нужно, чтобы цифры были введены в числовом порядке
- Не заботьтесь, если 1 дано в начале или нет
- Не заботьтесь о том, даны ли простые числа.
Я полагаю, что это можно сделать с помощью умного рекурсивного генератора...
Так, например, вызов composites_with_factors (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). Когда все комбинации с THAT prime сделаны, отбросьте его и повторите со следующим самым низким простым числом, доступным на генераторе простых чисел.
Мои попытки сделать это с помощью "рекурсивных генераторов" заставили меня очень смутить, когда выходить из рекурсии с помощью "yield" или "raise StopIteration" или "return" или просто выпадать из рекурсивной функции.
Спасибо за вашу мудрость!
ДОПОЛНИТЕЛЬНОЕ ПРИМЕЧАНИЕ:
У меня есть один способ сделать это сейчас: я написал функцию для чисел с коэффициентами, поэтому я могу разложить их на простые числа и дать результаты. Нет проблем. Я держу это невероятно быстро, полагаясь на кеш "того, что является самым низким основным фактором числа N"... для N до 10 миллионов.
Однако, как только я выйду из кеша, мы перейдем к "наивному" факторингу. (Тьфу.)
Пункт этого сообщения:
- Я предполагаю, что "генерация больших композитов из их факторов" будет быстрее, чем "факторинг больших композитов"... тем более, что я НЕ забочусь о порядке и
- Как вы можете заставить генератор Python "рекурсивно" называть себя и давать один поток генерируемых вещей?