efficiente generare tutti i numeri composti meno di N (con i loro fattorizzazione)

Question

mi piacerebbe costruire un efficiente Python iteratore/generatore che produce:

• Tutti i numeri composti meno di N
• Insieme con il loro primo fattorizzazione

io chiamo "composites_with_factors()"

Assumere abbiamo già una batteria Li st di numeri primi meno di N, o un generatore di primi che può fare lo stesso.

Nota che:

• non hanno bisogno i numeri per essere ceduto in ordine numerico
• Non mi importa se 1 viene ceduto all'inizio o no
• non mi importa se stanno ceduto numeri primi anche

Immagino che questo può essere fatto con un generatore di ricorsiva intelligente ...

Quindi, per esempio, una chiamata a composites_with_factors (16) può produrre:

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

Come si può vedere dalla fine della mia produzione, concepisco di questo lavoro avviando con il più piccolo privilegiata sul generatore di numeri primi disponibili, e l'output tutti i poteri di quel primo inferiore a N, quindi riprovare attraverso i poteri di quel primo, ma ad ogni stadio vedendo se posso applicare poteri di numeri primi aggiuntivi (e comunque essere inferiore a N). Quando tutte le combinazioni con THAT prime sono terminate, rilasciatelo e ripetete con il numero primo più basso disponibile sul generatore di primi.

I miei tentativi di fare questo con "generatori ricorsivi" mi hanno fatto molto confondere su quando uscire dalla ricorsione con "rendimento", o "aumentare StopIteration", o "tornare", o semplicemente cadere fuori dal rottame funzione.

Grazie per la tua saggezza!

Nota aggiuntiva:

ho fare hanno un modo per farlo ora: ho scritto una funzione di fattore numeri, quindi posso fattore giù per primi, e dare i risultati. Nessun problema. Lo tengo incredibilmente veloce basandomi su una cache di "qual è il fattore primo più basso del numero N" ... per N fino a 10 milioni.

Tuttavia, una volta uscito dal cache, lo faremo per il factoring "ingenuo". (. Yuck)

Il punto di questo post è:

• Sto assumendo che "la generazione di grandi dimensioni composti dai loro fattori" sarà più veloce di "factoring grandi compositi" ... soprattutto perché ho DON 'T cura dell'ordine, e
• Come si può avere un generatore Python "ricorsivamente" chiamandosi e producendo un singolo flusso di cose generate?

Answer 1

Supponendo primesiter(n) crea un iteratore su tutti i numeri primi fino a n (1 non dovrebbe essere incluso in primesiter, oa seguito di codice ben immettere inf. Anello)

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) 

uscita

>> 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: include anche n (= 16) e ho usato l'elenco al posto delle tuple. Entrambi possono essere risolti facilmente se necessario, ma lo lascerò come esercizio.

Answer 2

ricorsivamente (pseudo-codice):

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

Ecco un'implementazione setaccio-based (scusate il codice non-divinatorio :)):

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" 

Test:

>>> runTests() 
passed 
passed 
passed 

Sulla mia macchina ci sono voluti 56 secondi per eseguire:

primes = sieve(14000000) # 14 million! 

Esempi:

>>> 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 di memoria: circa 50 milioni di numeri interi, in 14 milioni di liste:

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