在不使用GCD方法的情況下找到共素數

如果不使用任何標準GCD算法，是否可以知道兩個給定數字是否是同素數？我已經使用歐幾里德二進制GCD & Lehmer算法。如果可能，建議一種比這更快的方法。兩個數字可以大到10^5，因此產生Faray序列也是沒有用的。在不使用GCD方法的情況下找到共素數

來源

2014-03-13 raul1rnjn535_3

它需要多快？在c＃中使用一個基本的GCD實現的coprime測試，對於隨機整數，平均只需要大約110納秒，直到32位整數的最大範圍。在你提到的範圍內，時間會更少。 – hatchet

我給了一個數組的數組，陣列的大小可以高達10^5，數組中的每個數字可以在最大10^5。這就是爲什麼我想要避免執行GCD –

我的觀點是GCD是沒有那麼糟糕的表現明智。發佈您迄今爲止使用的最快的代碼。它可能不是GCD，它可能是你的實現。有辦法提高性能。例如，這個初始位旋轉'（x | y）＆1'可以過濾掉兩個數字都是偶數的情況，這應該是給定隨機輸入時間的25％，並且幾乎不需要任何時間。 – hatchet

您可能會發現這兩種簡單實現之一比您在評論中鏈接到的功能更快。它是c＃代碼，但應該很容易轉換爲c或java。它們適用於unsigned int，但爲其他類型編寫版本應該很簡單。

public static uint Gcd(uint value1, uint value2) { 
    while (value1 != 0) { 
     uint t = value2 % value1; 
     value2 = value1; 
     value1 = t; 
    } 
    return value2; 
} 

public static uint GcdR(uint value1, uint value2) { 
    return (value1 == 0) ? value2 : GcdR(value2 % value1, value1); 
}

在似乎將因爲模運算符的比較慢，但是至少在C＃中，它比快兩倍，你鏈接的功能更多（將其轉換爲C＃後）。我發現第一個非遞歸版本稍快。您必須進行基準測試，以查看您使用的語言是否比您擁有的更快。使用Gcd的IsCoprime看起來像這樣

public static bool IsCoprime(this uint value1, uint value2) { 
    // 25% of possible pairings are even num to even num so handle them 
    // with a bit twiddle that's much faster than GCD function. If they 
    // are both even, then they can't be coprime (2 is common divisor). 
    return ((((value1 | value2) & 1) != 0) 
      && (Gcd(value1, value2) == 1)); 
}

來源

2014-03-14 22:48:09 hatchet

在不使用GCD方法的情況下找到共素數

回答

相關問題