Efficacement trouver tous les diviseurs d'un nombre

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

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    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<int>();
    return toreturn;
}

où les nombres premiers est une liste de nombres premiers (à supposer qu'il est correct, et est assez grand).
L'algorithme fonctionne dans le sens qu'il trouve tous les facteurs premiers, mais pas tous les facteurs (c'est à dire étant donné 34534, il retourne {1,2,17267,31,1114} mais rate {62, 557} 62 est une combinaison, et, par conséquent, manque 557.

J'ai aussi essayé simplement d'obtenir les facteurs premiers d'un nombre, mais je ne sais pas comment faire pour les convertir en une liste de toutes les corriger combinaisons.

Le code pour que l'algorithme est le suivant:

public static List<int> prime_factors(int x)
{
    List<int> toreturn = new List<int>();
    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ésoudre le premier, ou comment créer la liste des combinaisons à partir de la seconde (je préfère qu'il serait plus rapide)?

Double Possible de la Meilleure façon de trouver tous les facteurs d'un nombre donné en C#

OriginalL'auteur soandos | 2011-04-26

  1. 7

    Puisque vous avez déjà une liste de facteurs premiers, ce que vous voulez faire est de calculer l'ensemble des parties de cette liste.

    Maintenant, le problème est que vous risquez d'avoir des doublons dans la liste (par exemple, les facteurs premiers de 20 = 2 * 2 * 5), mais les jeux ne permettent pas de doublons. Donc, nous pouvons faire de chaque élément de la liste unique en la projetant à une structure de la forme {x, y}, où x est le premier et y est l'indice du 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 premier et y est l'indice dans la liste.

    Ensuite, nous calculons la puissance (définition de GetPowerSet ci-dessous):

    var power_set_primes = GetPowerSet(all_primes);

    Donc, power_set_primes est un IEnumerable<IEnumerable<T>> où T est le type anonyme {x, y} où x et y sont de type int.

    Ensuite, on calcule le produit de chaque élément de la puissance de

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

    Mettant 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<int>();

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

    De http://rosettacode.org/wiki/Power_Set pour les implémentations de l'ensemble des parties.

    public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> 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];
}
    Je n'ai pas le suivre. Les facteurs de la liste des facteurs premiers que j'ai trouvé? Et depuis ce que je veux, c'est toutes les combinaisons de facteurs qui se multiplient à moins de ou égal à ce nombre, il y a une meilleure façon.
    Opps, qui ne devrait pas être en Mathématiques.Étage... édition...
    cela ne fonctionne pas vraiment bien. actuellement, si un premier va en plus de lui-même fois, ce ne sera pas de donner la bonne facteurs (ce qui arrive souvent, c'est à dire à chaque fois 9 est un facteur...)
    Je n'ai pas besoin que... le fait qu'il existe de multiples copies du premier dans la liste retournée est plus que suffisant, puisque je besoin pour obtenir toutes les combinaisons dont le produit est moins que le nombre de toute façon
    Pour toutes les personnes qui consultent cela, il suffit de supprimer le .x, et le code fonctionne correctement

    OriginalL'auteur Rodrick Chapman

  2. 5

    Il y a eu une question similaire avant, qui a une solution intéressante à l'aide de IEnumerable. Si vous voulez tous les diviseurs et non pas les facteurs, et en supposant que vous utilisez au moins de C# 3.0, vous pouvez utiliser quelque chose comme ceci:

    static IEnumerable<int> 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<int> divisors = GetDivisors(10).ToList();
    encore une fois, c'est un bon moyen de le faire à la force brute. mais étant donné que j'ai une liste de la nécessaire nombres premiers, il n'y a pas de raison de le faire de cette façon.
    Donc, si vous avez tous les facteurs premiers du nombre et de la juste envie de toutes les combinaisons entre eux pourquoi pas à l'aide d'un produit cartésien, sorte de: from x in primes from y in primes where x != y select x * y? Cela pourrait résoudre votre problème, à condition que vous ayez 1 dans votre nombre premier (sinon une .Concat(nombres premiers) permettrait de résoudre ce)
    Comment dois-je faire?
    mais le nombre de facteurs que j'ai multiplier est inconnu. il pouvait être trois ou plus...
    Je vois votre point de vue. Ce que vous demandez est une méthode pour avoir toutes les combinaisons possibles de facteurs premiers que vous avez déjà. Ceci peut être résolu par le biais de certains combinatoire algorithme qui, à mon avis, n'est pas simple à mettre en œuvre correctement. En outre, vous risquez de finir avec une solution qui, tout en essayant d'optimiser la vitesse, les risques d'être moins performantes qu'une approche plus simple, et beaucoup moins lisible. Peut-être que vous pourriez envisager d'écriture lisible une solution d'abord, et ensuite essayer de l'optimiser si sa performance n'est pas acceptable pour la tâche donnée.

    OriginalL'auteur LazyOfT