C++でのGCD関数sans cmathライブラリ

Question

私は混合数値クラスを作成していて、すばやく簡単な「最大公約数」関数が必要です。誰か私にコードやコードへのリンクを教えてもらえますか？

Answer 1

私は投票に賛成できません。実装を見つけるのは難しいと信じるのは難しいようですが、確かに分かっています。

unsigned GCD(unsigned u, unsigned v) { 
    while (v != 0) { 
     unsigned r = u % v; 
     u = v; 
     v = r; 
    } 
    return u; 
} 

Answer 2

迅速な再帰バージョン：

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2); 
} 

または同等の反復バージョンあなたが激しく再帰^{に反対している場合（a）の}：自分で

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    unsigned int tmp; 
    while (n2 != 0) { 
     tmp = n1; 
     n1 = n2; 
     n2 = tmp % n2; 
    } 
    return n1; 
} 

だけで代用（例えば、bignumクラスのような非基本型を使用している場合）、データ型、ゼロ比較、代入、モジュラスの各メソッドがあります。

この関数は実際には画面サイズの積分アスペクト比を計算するためにearlier answer of mineから来ましたが、元のソースは長い時間前に学んだユークリッドアルゴリズムでした。詳細はhere on Wikipediaです。

---

^{（a）は、いくつかの再帰的なソリューションと}問題は、あなたがそこに着く前に、彼らはこのように非常に悪い考え抜か（擬似のように、あなたはスタック領域が不足する傾向があるので、ゆっくりと答えに近づくということですコード）：あなたは（）億を使い切るかそこらのフレームをスタックしようとして

def sum (a:unsigned, b:unsigned): 
    if b == 0: return a 
    return sum (a + 1, b - 1) 

あなたはsum (1, 1000000000)のようなものには、非常に高価な見つけることができます。再帰の理想的なユースケースはバイナリ検索のようなもので、反復ごとにソリューションの領域を半分に減らします。最大公約数は、解空間が急速に縮小され、大量のスタック使用に関する不安がそこに根付いていないものです。

Answer 3

EuclideanアルゴリズムはのlibstdC++アルゴリズムライブラリは、（私はG ++ 4.6.3を使用しています）隠しGCD機能を持つC.

に

int gcd(int a, int b) { 
    while (b != 0) { 
    int t = b; 
    b = a % b; 
    a = t; 
    } 
    return a; 
} 

Answer 4

書くことは非常に簡単です。

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    cout << std::__gcd(100,24); 
    return 0; 
} 

あなたは

UPDATE歓迎:)です：@のchema989はC++ 17で、それを指摘したように<numeric>ヘッダーで使用可能なstd::gcd()機能があります。

Answer 5

私の2セント。符号なし整数型のためXOR swapを使用してテンプレートユークリッドアルゴリズム：

template <class Unsigned> 
Unsigned gcd(Unsigned a, Unsigned b) 
{ 

    static_assert(
     std::numeric_limits<Unsigned>::is_integer && 
     !std::numeric_limits<Unsigned>::is_signed, "Unsigned required."); 

    while (b) 
    { 
     b ^= a; 
     a ^= b; 
     b = (b^a) % a; 
    } 
    return a; 
} 

Answer 6

ヘッダ<numeric>で定義されたstd::gcdあなたが使用できる17 C++の場合：ところで

auto res = std::gcd(10, 20);