Trouver efficacement tous les diviseurs d’un nombre

Je veux donc simplement trouver tous les diviseurs d’un nombre donné (à l’exception du nombre lui-même). Actuellement, j’ai ceci:

public static List proper_divisors(int x) { List toreturn = new List(); toreturn.Add(1); int i = 0; int j=1; int z = 0; while (primes.ElementAt(i) < Math.Sqrt(x)) { if (x % primes.ElementAt(i) == 0) { toreturn.Add(primes.ElementAt(i)); toreturn.Add(x / primes.ElementAt(i)); j = 2; z = (int)Math.Pow(primes.ElementAt(i), 2); while (z < x) { if (x % z == 0) { toreturn.Add(z); toreturn.Add(x / z); j++; z = (int)Math.Pow(primes.ElementAt(i), j); } else { z = x; } } } i++; } toreturn = toreturn.Distinct().ToList(); return toreturn; }

où primes est une liste de nombres premiers (supposons qu’elle est correcte et suffisamment grande). L’algorithme fonctionne dans le sens où il trouve tous les facteurs premiers, mais pas tous (c’est-à-dire donné 34534, il retourne {1,2,17267,31,1114} mais manque {62, 557}, car 62 est une combinaison, et manque donc 557 aussi.

J’ai également essayé d’obtenir les facteurs premiers d’un nombre, mais je ne sais pas comment convertir cela en une liste de toutes les combinaisons correctes.

Le code pour cet algorithme est le suivant:

 public static List prime_factors(int x) { List toreturn = new List(); int i = 0; while (primes.ElementAt(i) <= x) { if (x % primes.ElementAt(i) == 0) { toreturn.Add(primes.ElementAt(i)); x = x / primes.ElementAt(i); } else { i++; } } return toreturn; }

Des idées sur la façon de réparer le premier ou sur la façon de créer la liste de combinaisons à partir du second (je préférerais cela, car ce serait plus rapide)?

Puisque vous avez déjà une liste des facteurs premiers, vous voulez en calculer le pouvoir.

Maintenant, un problème est que vous pouvez avoir des doublons dans la liste (par exemple, les facteurs premiers de 20 = 2 * 2 * 5), mais les ensembles ne permettent pas les doublons. Ainsi, nous pouvons rendre chaque élément de la liste unique en le projetant dans une structure de la forme {x, y} où x est le nombre premier et y est l’indice du nombre premier dans la liste.

 var all_primes = primes.Select((x, y) => new { x, y }).ToList();

Maintenant, all_primes est une liste de la forme {x, y} où x est le nombre premier et y est l’index de la liste.

Ensuite, nous calculons le pouvoir défini (définition de GetPowerSet ci-dessous):

 var power_set_primes = GetPowerSet(all_primes);

Par conséquent, power_set_primes est un IEnumerable> où T est le type anonyme {x, y} où x et y sont de type int .

Ensuite, nous calculons le produit de chaque élément du groupe de puissance

 foreach (var p in power_set_primes) { var factor = p.Select(x => xx).Aggregate(1, (x, y) => x * y); factors.Add(factor); }

Mettre tous ensemble:

 var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates. var power_set_primes = GetPowerSet(all_primes); var factors = new HashSet(); foreach (var p in power_set_primes) { var factor = p.Select(x => xx).Aggregate(1, (x, y) => x * y); factors.Add(factor); }

De http://rosettacode.org/wiki/Power_Set pour les implémentations de powerset.

 public IEnumerable> GetPowerSet(List list) { return from m in Enumerable.Range(0, 1 << list.Count) select from i in Enumerable.Range(0, list.Count) where (m & (1 << i)) != 0 select list[i]; }

Il y avait une question similaire avant , qui a une solution intéressante en utilisant IEnumerable. Si vous voulez tous les diviseurs et non les facteurs, et en supposant que vous utilisez au moins C # 3.0, vous pouvez utiliser quelque chose comme:

 static IEnumerable GetDivisors(int n) { return from a in Enumerable.Range(2, n / 2) where n % a == 0 select a; }

et ensuite l’utiliser comme ceci:

 foreach(var divisor in GetDivisors(10)) Console.WriteLine(divisor);

ou, si vous voulez une liste, il suffit de:

 List divisors = GetDivisors(10).ToList();