The most efficent way to get all divisors of a number

Question

Possible Duplicate:
Efficiently finding all divisors of a number

This is much more of an efficiency question than a generic "find a way to do it", but after getting some odd results, I want to see if someone can tell me why the last way is so inefficient:

way 1: brute force, no optimization

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

way 2: same as before, but this time, check if its prime first (as those cases take up the most time, using miller-rabin for prime checking)

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

what it thought would be the fastest way by far was way 3, because it reduced the number that it was working with every time it found a prime factor, and it only tried primes (these were generated by a sieve at runtime, takes about 34 ms to get all primes less than a million) the last thing this way had to do was take the prime factors and their powers, and make a list of all the factors.

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

Time it took to factor the first million numbers: way 1: 7223 ms way 2: 8985 ms (prime checking is not worth it for small numbers i guess) way 3: 49423 ms

so my question is twofold: 1) why is way 3 so slow??? 2) is there something that can make it faster? as an aside, primes was computed as a list, then converted to an array, as I thought it would be faster that way. bad move?

Answer 1

This is the problem domain of integer factorization. There are a number of wellknown algorithms here:

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

I suggest you pick the best match + profile.

---

my original comment:

Profile profile profile. Also, don't use enumerators or LINQ if you care about efficiency there. Write it in C and use P/Invoke. In general, don't ask the question if you can measure it