最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方式來獲得一個號碼的所有約數

回答

相關問題