eficientemente generar todos los números compuestos inferior a N (con sus factorizaciones)

Question

me gustaría construir un pitón eficiente iterador/generador que produce:

• Todos los números compuestos inferior a N
• Junto con su mejor momento factorización

lo llamaré "composites_with_factors()"

Asumir que ya tenemos un li st de primos menor que N, o un generador de primos que puede hacer lo mismo.

Nota que:

• no necesita los números que se produjo en orden numérico
• no me importa si es 1 se produjo al comienzo o no
• no les importa si sean cedidos números primos también

calculo esto se puede hacer con un generador recursiva inteligente ...

Por lo tanto, por ejemplo, una llamada a composites_with_factors (16) puede producir:

# 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) 

Como se puede ver en el orden de mi salida, concibo de este trabajo, comenzando con el primo más pequeño en el generador de números primos disponibles, y la salida de todos los poderes de ese primo menor que N, luego intente de nuevo a través de los poderes de ese primo pero en cada etapa viendo si puedo aplicar poderes de primos adicionales (y aún ser menor que N). Cuando se hayan realizado todas las combinaciones con ESTE primo, suéltelo y repítalo con el siguiente número primo más bajo disponible en el generador de primos.

Mis intentos de hacer esto con "generadores recursivos" me han confundido mucho sobre cuándo salir de la recursión con "rendimiento", o "levantar StopIteration", o "devolver", o simplemente caer de las recursivas función.

¡Gracias por su sabiduría!

NOTA ADICIONAL:

que hacer tienen una manera de hacer esto ahora: He escrito una función para factorizar números, por lo que puede factorizar hacia abajo a números primos, y dar los resultados. No hay problema. Lo mantengo increíblemente rápido confiando en un caché de "cuál es el factor primo más bajo del número N" ... para N hasta 10 millones.

Sin embargo, una vez que estoy fuera del caché, pasaremos al factoring "ingenuo". (. Yuck)

El punto de este post es:

• Estoy asumiendo que "la generación de grandes materiales compuestos a partir de sus factores" será más rápido que "factorización de grandes materiales compuestos" ... sobre todo porque yo DON 'T se preocupan por el orden, y
• ¿Cómo se puede tener un generador de Python "recursivamente" a sí mismo, y producir una sola secuencia de cosas generadas?

Answer 1

Suponiendo primesiter(n) crea un iterador sobre todos los primos hasta n (1 no debería incluirse en primesiter, o después de código bien entran inf. Bucle)

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) 

salida

>> 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])] 

NOTA: también incluye n (= 16) y utilicé list en lugar de tuplas. Ambos pueden resolverse fácilmente si es necesario, pero lo dejaré como un ejercicio.

Answer 2

de forma recursiva (pseudo-código):

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) 

Answer 3

Aquí es una aplicación basada en el tamiz (Por favor, disculpe el código anti-Pythonic :)):

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" 

Pruebas:

>>> runTests() 
passed 
passed 
passed 

En mi máquina, esto demoró 56 segundos en ejecutarse:

primes = sieve(14000000) # 14 million! 

Ejemplos:

>>> 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] 

consumo de memoria: unos 50 millones de números enteros, en 14 millones de listas:

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