最efficent方式来获得一个号码的所有约数

可能重复：
Efficiently finding all divisors of a number 最efficent方式来获得一个号码的所有约数

这是比一般的更效率问题“找到一个方法来做到这一点“，但在得到一些奇怪的结果后，我想看看有人能告诉我为什么最后一种方式效率太低：

方式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：和以前一样，但是这一次，检查其引发第一（因为这种情况下占用的时间最多，用米勒 - 拉宾为主要检查）

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

什么思想将是目前最快的方法，因为它减少了每次发现主要因素时所使用的数量，并且它只尝试了素数（这些数据是在运行时通过筛选产生的，大约需要34 ms才能获得所有素数都低于一百万），这种方式所做的最后一件事是采取主要因素和权力，并列出所有因素。

方式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）有什么可以使它更快？除此之外，素数计算为一个列表，然后转换为一个数组，因为我认为这样会更快。不好的举动？

来源

2011-04-28 soandos

你不问这个问题吗？ http://stackoverflow.com/questions/5793009/efficiently-finding-all-divisors-of-a-number – 2011-04-28 13:05:27

配置文件配置文件。另外，如果你关心那里的效率，不要使用枚举器或LINQ。用C编写并使用P/Invoke。一般来说，不要问这个问题，如果你可以测量它 – sehe 2011-04-28 13:09:33

请使用像“结果”，而不是“返回”的东西。 – MrFox 2013-02-20 16:49:00

这是整数分解的问题域。有许多的知名算法在这里：

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

我建议你挑选最佳匹配+个人资料。

我原来的评论：

个人资料简介资料。另外，如果你关心那里的效率，不要使用枚举器或LINQ。用C编写并使用P/Invoke。一般来说，不要问这个问题，如果你能测量它

来源

2011-04-28 13:11:40 sehe

最efficent方式来获得一个号码的所有约数

回答

相关问题