Trova tutti i fattori (primo e composto) di un numero

Naviga le tue risposte
2

Possiamo trovare tutti i fattori primi usando un setaccio di erastoteni. Ma come troviamo TUTTI i fattori di un numero?

Ad esempio, 24 = 2x2x2x3

Ma la lista completa dei fattori è - 1,2,3,4,6,8,12,24.

Sto pensando di spingere tutti i fattori in un vettore, quindi usando una maschera di bit per ottenere ogni sottoinsieme. I problemi con questo approccio sono -

  1. La complessità sarà O (n). Per n = 10 ^ 10, ci sono 35 fattori, quindi 2 ^ 35 set di fattori, che è 10 ^ 10.

  2. Sottoinsiemi ripetuti. Come nell'esempio sopra, otteniamo più sottoinsiemi con gli stessi fattori ripetuti, come (22 ....), (2.2 ...), (2..2 ..), ecc. Come rimuovere questa ridondanza?

posta goelakash 10.04.2015 - 08:01
fonte

1 risposta

2

La soluzione più semplice: 

for i = 1 to sqrt(n)
   if i divides n put i and n/i into your result set 
      (make sure if i=n/i you put it only once there)

Complessità: O (sqrt (n))

(finché non lavori con numeri grandi e puoi assumere tutte le operazioni aritmetiche di base come test per divisibilità come O (1).

Un algoritmo più sofisticato è descritto qui . Primo, trova tutti i fattori primi di n compresi i loro poteri che dividono n (usando il Sieve di Erastothenes). Quindi, crea tutte le combinazioni di questi fattori, come descritto nel post del blog.

    
risposta data 10.04.2015 - 08:11
fonte

Leggi altre domande sui tag

Posso avere più di una descrizione per specifica di prova? Gestire la fine del ciclo di sprint tra tester e sviluppatori [duplicato]