Самый эффективный способ получить все делители числа

Question

Возможный дубликат:
Эффективно найти все делители числа

Это гораздо больше вопрос эффективности, чем общий "найти способ сделать это", но после получения некоторых странных результатов, я хочу посмотреть, может ли кто-нибудь сказать мне, почему последний способ так неэффективен:

способ 1: грубая сила, без оптимизации

    public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
        {
            if (x % i == 0)
            {
                toreturn.Add(i);
                toreturn.Add(x / i);
            }
        }
        if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
        {
            toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
        }

        return toreturn;
    }

способ 2: такой же, как и раньше, но на этот раз проверьте, является ли его простое число первым (так как эти случаи занимают больше всего времени, используя miller-rabin для первичной проверки)

        public static List<int> proper_divisors(int x)
    {
        List<int> toreturn = new List<int>();
        if (!isprime(x))
        {
            for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++)
            {
                if (x % i == 0)
                {
                    toreturn.Add(i);
                    toreturn.Add(x / i);
                }
            }
            if (toreturn.ElementAt(toreturn.Count() / 2) == toreturn.ElementAt(toreturn.Count() / 2 - 1))
            {
                toreturn.Remove(toreturn.ElementAt(toreturn.Count() / 2));
            }
        }
        else
        {
            toreturn.Add(1);
            toreturn.Add(x);

        }
        return toreturn;
    }

то, что он считал самым быстрым, безусловно, был путь 3, потому что он уменьшал число, с которым работал, каждый раз, когда находил главный фактор, и он пробовал только простые числа (они были созданы ситом во время выполнения, занимает около 34 мс, чтобы получить все простые числа менее миллиона) последнее, что нужно было сделать таким образом, - это взять главные факторы и их силы и составить список всех факторов.

способ 3:

                public static HashSet<int> prime_factors(int x)
    {
        if (!isprime(x))
        {
            List<int> toreturn = new List<int>();
            int i = 0;
            while (primes[i] <= x)
            {
                if (x % primes[i] == 0)
                {
                    toreturn.Add(primes[i]);
                    x = x / primes[i];
                }
                else
                {
                    i++;
                }
            }
            var power_set_primes = GetPowerSet(toreturn);
            var factors = new HashSet<int>();
            foreach (var p in power_set_primes)
            {
                var factor = p.Select(z => z).Aggregate(1, (z, y) => z * y);
                factors.Add(factor);
            }
            return factors;
        }
        else
        {
            HashSet<int> toreturn = new HashSet<int>();
            toreturn.Add(1);
            toreturn.Add(x);
            return toreturn;
        }
        public static 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];
    }

Время, которое потребовалось для вычисления первого миллиона чисел: путь 1: 7223 мс, путь 2: 8985 мс (первичная проверка не стоит больших чисел, я полагаю) путь 3: 49423 мс

поэтому мой вопрос двоякий: 1) почему путь 3 такой медленный??? 2) есть ли что-то, что может сделать это быстрее? кроме того, простые числа были вычислены как список, а затем преобразованы в массив, так как я думал, что так будет быстрее. плохой ход?

Answer 1

Это проблемная область целочисленной факторизации. Здесь есть ряд известных алгоритмов:

http://en.wikipedia.org/wiki/Integer_factorization

Я предлагаю вам выбрать лучший матч + профиль.

---

мой оригинальный комментарий:

Профиль профиль профиль. Кроме того, не используйте перечислители или LINQ, если вы заботитесь об эффективности там. Запишите это на C и используйте P / Invoke. В общем, не задавайте вопрос, если вы можете измерить его