Possible duplicate:
Effectively find all the divisors of the number
This is a much more efficient question than the general “find a way to do this,” but after getting some odd results, I want to see if anyone can tell me why the latter method is so inefficient:
method 1: brute force, without 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; }
path 2: the same as before, but this time check if it is primary first (since these cases take the most time, using the miller-rabin for a simple check)
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, in his opinion, would be the fastest way, was method 3, as he reduced the number with which he worked every time he found the main factor, and he only tried prime numbers (they were created by a sieve at runtime takes about 34 ms to get all primes less than a million). The last thing to do was to take the main factors and their authority and make a list of all the factors.
method 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 spent on the factor of the first million numbers: path 1: 7223 ms path 2: 8985 ms (the usual check is not worth it for small numbers, I think) path 3: 49423 ms
so my question is twofold: 1) why is path 3 so slow ??? 2) is there something that can make it faster? as an exception, primes were calculated as a list and then converted to an array, as I thought it would be faster. bad move?