Эффективно генерировать все составные числа меньше N (с их факторизацией)

Я бы хотел создать эффективный итератор/генератор 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 "рекурсивно" называть себя и давать один поток генерируемых вещей?

Ответы

Ответ 1

Предполагая, что primesiter(n) создает итератор по всем простым числам до n (1 НЕ следует включать в primesiter или следующий код хорошо вводить петлю)

def composite_value(n, min_p = 0):
    for p in primesiter(n):
        # avoid double solutions such as (6, [2,3]), and (6, [3,2])
        if p < min_p: continue
        yield (p, [p])
        for t, r in composite_value(n//p, min_p = p): # uses integer division
            yield (t*p, [p] + r)

Выход

>> list(composite_value(16))
[(2, [2]),
 (4, [2, 2]),
 (8, [2, 2, 2]),
 (16, [2, 2, 2, 2]),
 (12, [2, 2, 3]),
 (6, [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 (= 16), и я использовал список вместо кортежей. Оба могут быть легко разрешены, если это необходимо, но я оставлю это как упражнение.

Ответ 2

Вот реализация на основе сита (пожалуйста, извините непифонный код:)):

def sieve(n):
    # start each number off with an empty list of factors
    #   note that nums[n] will give the factors of n
    nums = [[] for x in range(n)]
    # start the counter at the first prime
    prime = 2
    while prime < n:
        power = prime
        while power < n:
            multiple = power
            while multiple < n:
                nums[multiple].append(prime)
                multiple += power
            power *= prime
        # find the next prime
        #   the next number with no factors
        k = prime + 1
        if k >= n:    # no primes left!!!
            return nums
        # the prime will have an empty list of factors
        while len(nums[k]) > 0:
            k += 1
            if k >= n:    # no primes left!!!
                return nums
        prime = k
    return nums


def runTests():
    primes = sieve(100)
    if primes[3] == [3]:
        print "passed"
    else:
        print "failed"
    if primes[10] == [2,5]:
        print "passed"
    else:
        print "failed"
    if primes[32] == [2,2,2,2,2]:
        print "passed"
    else:
        print "failed"

Тесты:

>>> runTests()
passed
passed
passed

На моей машине это заняло 56 секунд для запуска:

primes = sieve(14000000) # 14 million!

Примеры:

>>> primes[:10]
[[], [], [2], [3], [2, 2], [5], [2, 3], [7], [2, 2, 2], [3, 3]]

>>> primes[10000]
[2, 2, 2, 2, 5, 5, 5, 5]

>>> primes[65536]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

>>> primes[6561]
[3, 3, 3, 3, 3, 3, 3, 3]

>>> primes[233223]
[3, 17, 17, 269]

Потребление памяти: около 50 миллионов целых чисел, в 14 миллионах списков:

>>> sum(map(len, primes))
53303934

Ответ 3

Рекурсивно (псевдокод):

def get_factorizations_of_all_numbers( start = starting_point
                                     , end = end_point
                                     , minp = mimimum_prime
                                     ):
    if start > end:
        return Empty_List
    if minp ^ 2 > end:
        return list_of_all_primes( start, end )
    else
        a = minp * get_factorizations_of_all_numbers( rounddown(start/minp)
                                                    , roundup(end/minp)
                                                    )
        b = get_factorizations_of_all_numbers( start
                                             , end
                                             , next_prime( minp )
                                             )
        return append( a , b )

get_factorizations_of_all_numbers( 1, n, 2 )