Эффективно найти все делители числа - PullRequest
Новая
       42

Эффективно найти все делители числа

10 голосов
/ 26 апреля 2011

Так что я просто хочу найти все делители данного числа (за исключением самого числа). В настоящее время у меня есть это: 

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;
}

где простые числа - это список простых чисел (предположим, что это правильно и достаточно велико). Алгоритм работает в том смысле, что он находит все основные факторы, но не все факторы (то есть, учитывая 34534, он возвращает {1,2,17267,31,1114}, но пропускает {62, 557}, поскольку 62 является комбинацией, и поэтому также пропускает 557.

Я также пытался получить простые множители числа, но я не знаю, как преобразовать это в список всех правильных комбинаций.

Код для этого алгоритма выглядит следующим образом: 

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;
}

Любые идеи о том, как исправить первое или как создать список комбинаций из второго (я бы предпочел, чтобы оно было быстрее)?

Ответы [ 2 ]

7 голосов
/ 26 апреля 2011

Поскольку у вас уже есть список основных факторов, вы хотите вычислить набор параметров этого списка.

Теперь одна проблема состоит в том, что в списке могут быть дубликаты (например, простые множители 20 = 2 * 2 * 5), но наборы не допускают дубликатов.Таким образом, мы можем сделать каждый элемент списка уникальным, проецируя его на структуру вида {x, y}, где x - простое число, а y - индекс простого числа в списке. 

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

Теперь all_primes - это список вида {x, y}, где x - это простое число, а y - индекс в списке.

Затем мы вычисляем набор мощности (определение GetPowerSet ниже): 

var power_set_primes = GetPowerSet(all_primes);

Следовательно, power_set_primes является IEnumerable<IEnumerable<T>>, где T является анонимным типом {x, y}, где x и y имеют тип int.

Далее, мы вычисляем произведение каждого элемента в наборе питания 

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

Собираем все вместе: 

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);
}

От http://rosettacode.org/wiki/Power_Set для реализации powerset. 

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];
}
5 голосов
/ 26 апреля 2011

Был похожий вопрос до , в котором есть интересное решение с использованием IEnumerable.Если вам нужны все делители, а не факторы, и если вы используете как минимум C # 3.0, вы можете использовать что-то вроде этого: 

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

, а затем использовать это так: 

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

или, если вы хотите список, просто: 

List<int> divisors = GetDivisors(10).ToList();
...