Il modo migliore per trovare tutti i fattori di un determinato numero

Tutti i numeri che si dividono uniformsmente in x.

Inserisco 4 restituisce: 4, 2, 1

edit: so che sembra un compito. Sto scrivendo una piccola app per popolare alcune tabelle di prodotti con dati di test semi-casuali. Due delle proprietà sono ItemMaximum e Item Multiplier. Devo assicurarmi che il moltiplicatore non crei una situazione illogica in cui l’acquisto di un altro articolo potrebbe mettere l’ordine oltre il massimo consentito. Quindi i fattori forniranno un elenco di valori validi per i miei dati di test.

edit ++: questo è quello che ho seguito dopo tutto l’aiuto di tutti. Grazie ancora!

edit #: Ho scritto 3 versioni diverse per vedere quale mi è piaciuto di più e le ho testate contro la fattorizzazione di numeri piccoli e numeri molto grandi. Incollerò i risultati.

static IEnumerable GetFactors2(int n) { return from a in Enumerable.Range(1, n) where n % a == 0 select a; } private IEnumerable GetFactors3(int x) { for (int factor = 1; factor * factor <= x; factor++) { if (x % factor == 0) { yield return factor; if (factor * factor != x) yield return x / factor; } } } private IEnumerable GetFactors1(int x) { int max = (int)Math.Ceiling(Math.Sqrt(x)); for (int factor = 1; factor < max; factor++) { if(x % factor == 0) { yield return factor; if(factor != max) yield return x / factor; } } } 

In zecche Quando si calcola il numero 20, 5 volte ciascuno:

  • GetFactors1-5,445,881
  • GetFactors2-4,308,234
  • GetFactors3-2,913,659

Quando si calcola il numero 20000, 5 volte ciascuno:

  • GetFactors1-5,644,457
  • GetFactors2-12,117,938
  • GetFactors3-3,108,182

pseudocodice:

  • Passa da 1 alla radice quadrata del numero, chiama l’indice “i”.
  • se numero mod i è 0, aggiungi i e number / i alla lista dei fattori.

realocode:

 public List Factor(int number) { List factors = new List(); int max = (int)Math.Sqrt(number); //round down for(int factor = 1; factor <= max; ++factor) { //test from 1 to the square root, or the int below it, inclusive. if(number % factor == 0) { factors.Add(factor); if(factor != number/factor) { // Don't add the square root twice! Thanks Jon factors.Add(number/factor); } } } return factors; } 

Come ha detto Jon Skeet, è ansible implementarlo come IEnumerable e utilizzare invece yield anziché aggiungere a un elenco. Il vantaggio con List è che potrebbe essere ordinato prima del reso, se necessario. Inoltre, è ansible ottenere un enumeratore ordinato con un approccio ibrido, ottenendo il primo fattore e memorizzando il secondo in ogni iterazione del ciclo, quindi restituendo ciascun valore memorizzato in ordine inverso.

Dovrai anche fare qualcosa per gestire il caso in cui un numero negativo è passato alla funzione.

L’operatore % (resto) è quello da usare qui. Se x % y == 0 allora x è divisibile per y . (Supponendo che 0 < y <= x )

Lo implementerei personalmente come metodo per restituire un object IEnumerable utilizzando un blocco iteratore.

Molto tardi ma la risposta accettata (qualche tempo fa) non ha dato i risultati corretti.

Grazie a Merlyn, ora ho ottenuto il motivo per il quadrato come un “massimo” sotto il campione corretto. anche se la risposta di Echostorm sembra più completa.

  public static IEnumerable getFactors(uint x) { for (uint i = 1; i*i <= x; i++) { if (0 == (x % i)) { yield return i; if (i != (x / i)) { yield return x / i; } } } } 

Come metodi di estensione:

  public static bool Divides(this int potentialFactor, int i) { return i % potentialFactor == 0; } public static IEnumerable Factors(this int i) { return from potentialFactor in Enumerable.Range(1, i) where potentialFactor.Divides(i) select potentialFactor; } 

Ecco un esempio di utilizzo:

  foreach (int i in 4.Factors()) { Console.WriteLine(i); } 

Nota che ho ottimizzato per chiarezza, non per le prestazioni. Per grandi valori di i questo algoritmo può richiedere molto tempo.

Un altro stile LINQ e che si lega per mantenere la complessità di O (sqrt (n))

  static IEnumerable GetFactors(int n) { Debug.Assert(n >= 1); var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1))) where n % i == 0 select new { A = i, B = n / i }; foreach(var pair in pairList) { yield return pair.A; yield return pair.B; } } 

L’ho fatto in modo pigro. Non ne so molto, ma mi è stato detto che la semplicità a volte può implicare l’eleganza. Questo è un modo ansible per farlo:

  public static IEnumerable GetDivisors(int number) { var searched = Enumerable.Range(1, number) .Where((x) => number % x == 0) .Select(x => number / x); foreach (var s in searched) yield return s; } 

EDIT : Come sottolineato da Kraang Prime, questa funzione non può superare il limite di un intero ed è (certamente) non il modo più efficiente per gestire questo problema.

Eccolo di nuovo, contando solo sulla radice quadrata, come altri hanno menzionato. Suppongo che le persone siano attratte da questa idea se speri di migliorare le prestazioni. Preferisco scrivere codice elegante per primo, e ottimizzare per le prestazioni in seguito, dopo aver testato il mio software.

Ancora, per riferimento, eccolo qui:

  public static bool Divides(this int potentialFactor, int i) { return i % potentialFactor == 0; } public static IEnumerable Factors(this int i) { foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i)) where potentialFactor.Divides(i) select potentialFactor) { yield return result; if (i / result != result) { yield return i / result; } } } 

Non solo il risultato è considerevolmente meno leggibile, ma anche i fattori vengono fuori ordine in questo modo.

E un’altra soluzione. Non sono sicuro che abbia qualche vantaggio oltre a essere leggibile ..:

 List GetFactors(int n) { var f = new List() { 1 }; // adding trivial factor, optional int m = n; int i = 2; while (m > 1) { if (m % i == 0) { f.Add(i); m /= i; } else i++; } // f.Add(n); // adding trivial factor, optional return f; } 

Non avrebbe senso iniziare alle 2 e dirigersi verso un valore limite superiore che viene continuamente ricalcolato in base al numero che hai appena controllato? Vedi N / i (dove N è il numero che stai cercando di trovare il fattore di e i è il numero corrente da verificare …) Idealmente, invece di mod, dovresti usare una funzione di divisione che restituisce anche N / i come ogni resto potrebbe avere. In questo modo esegui un’operazione di divisione per ricreare il limite superiore e il resto per il controllo della divisione uniforms.

Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx

Se usi il doppio, il seguente funziona: usa un ciclo for che itera da 1 fino al numero che vuoi calcolare. In ogni iterazione, dividere il numero da prendere in considerazione da i. Se (numero / i)% 1 == 0, allora i è un fattore, così come il quoziente di numero / i. Metti uno o entrambi in una lista e hai tutti i fattori.

Soluzione Linq:

 IEnumerable GetFactors(int n) { Debug.Assert(n >= 1); return from i in Enumerable.Range(1, n) where n % i == 0 select i; }