查找列表中所有數字的最小整數

-1

有沒有辦法從列表中找到N個數字的最大公約數。查找列表中所有數字的最小整數

例如：有一個列表像4,24,64,80,40,1264等......我想要一個方法，我可以在列表中找到最大公約數。在上述情況下，它是最大公約數4。我想要的是一個動態解決方案，它可以在列表中工作並給出價值。（一個整數除以列表中的所有數字而不提醒）

該解決方案可以是任何語言，C＃最好（利用Linq）。

PS：對不起，如果你認爲這屬於math.stackexchange.com，我真的混淆了其中哪些發佈到。

編輯：對不起，我的無知，我最初使用LCD。

來源

2014-02-10 Flamy

我就開始閱讀http://en.wikipedia.org/wiki/ Greatest_common_divisor - 它應該告訴你你需要知道什麼來實現這個（Euclid的算法），並且你可能還想確保你清楚最大公約數和最小公倍數之間的差異和聯繫。 – mcdowella

可能是你的意思是最大的共同點除數？因爲4> 2 – Herokiller

對不起我的無知。 – Flamy

執行以下操作： -

在列表中找到的最小號S。

找到S.

的所有素因子對每個素PI找到XI =最小（K1，K2，K3，...）其中Ki爲在ARR [I]

GCD = X1數pi的功率* X2 * .. XK

注：你可以在任何迭代3中時停止き= 1，因爲這將是最小的。

Java實現： -

public static long lgcd(long[] arr) { 

     long min = arr[0]; 

     for(int i=0;i<arr.length;i++) { 
      if(min>arr[i]) { 
       min = arr[i]; 
      } 
     } 

     ArrayList div_primes = new ArrayList(); 
     boolean isPrime[] = new boolean[(int)Math.sqrt(min)+1]; 
     for(int i=0;i<isPrime.length;i++) 
      isPrime[i] = true; 

     for(int j=2;j<isPrime.length;j++) { 
      if(isPrime[j]) { 
       int x = 2*j; 
       if(min%j==0) { 
        div_primes.add(j); 
       } 
       for(;x<isPrime.length;x=x+j) { 
        isPrime[x] = false; 
       } 
      } 
     } 

     if(div_primes.size()<1) { 
      div_primes.add(min); 
     } 

     long gcd = 1; 

     for(int i=0;i<div_primes.size();i++) { 
      long curr = (Integer)div_primes.get(i); 
      long x = min; 
      for(int j=0;j<arr.length;j++) { 
       long acc = arr[j]; 
       long fact = 1; 
       while(acc>1&&acc%curr==0) { 
        acc = acc/curr; 
        fact = fact*curr; 
       } 
       x = Math.min(x,fact); 
       if(fact==1) 
        break; 
      } 
      gcd = gcd*x; 
     } 
     return(gcd); 
    }

時間複雜度：

素數爲O計算（開方（S））

總質數約數爲O（日誌（ S））

GCD計算： - O（log（S）* N）

編輯：忘記添加角落情況下最小數本身是素數，以便添加以下代碼

if(div_primes.size()<1){ 
      div_primes.add(min); 
     }

來源

2014-02-10 15:05:52

您可以簡單地縮短列表的長度，然後運行一個循環來訪問每個值並在內部循環中將列表中的所有其他值分開，在每次成功的分割之後遞增計數器，然後將先前的計數與當前的如果當前計數較小，則內部循環存儲實際值。希望這可以解決您的問題

來源

2014-02-10 06:53:18

最小公倍數函數（LCM）是關聯和交換。因此，您可以通過簡單地執行以下操作來計算n個數字A的LCM。

k = 1 
for i = 1..n 
    k = LCM(k, A[i])

現有的LCM算法。看到這裏：http://en.m.wikipedia.org/wiki/Least_common_multiple

來源

2014-02-10 07:12:24

我想你想要的是Greatest Common Divisor(GCD)而不是Least Common Multiple(LCM)。您的示例的GCD和LCM應分別爲4和75840。

您可以通過prime factorization得到數字列表的GCD和LCM。它可以解碼爲動態解（通過記錄每個素因子的最小和最大指數）。把你的清單爲例：

4 = 2^2 
24 = 2^3 * 3 
64 = 2^6 
80 = 2^4 * 5 
40 = 2^3 * 5 
1264 = 2^4 * 79

所以GCD是2^2 = 4和LCM是2^6 * 3 * 5 * 79 = 75840。

來源

2014-02-10 07:19:14

兩個GCD和LCM計算這樣：

決心質數列表中的每個元素。如60 = 2^2 * 3 * 5。寫下這些主要表示爲向量。 As 60 =（2,1,1,0,0，..）
對於GCD，在所有表示中找到相同位置的最小值。重複所有職位。
對於LCM它將是最大的。
將這些表示方式轉回原點並將它們拼接起來。

據我記憶，這是學校六年級的課程。（12年 - 歲兒童）

來源

2014-02-10 11:22:46 Gangnus

查找列表中所有數字的最小整數

回答

相關問題