差分
ナビゲーションに移動
検索に移動
とりあえず作成
'''ユークリッドの互除法'''とは、2個の正の[[整数]]の[[最大公約数]]を比較的高速に求める[[アルゴリズム]]である。
==実装例==
===シンプルな実装===
<source lang="c">
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
</source>
===再帰を使わない実装===
<source lang="c">
int gcd(int a,int b) {
if(a<=0 || b<=0)return 0;
while(b>0) {
int t=a%b;
a=b;
b=t;
}
return a;
}
</source>
===[[Haskell]]による実装===
<source lang="haskell">
gcd a b = if b<=0 then a else gcd b (mod a b)
</source>
==関連項目==
* [[最大公約数]]
* [[最小公倍数]]
==実装例==
===シンプルな実装===
<source lang="c">
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
</source>
===再帰を使わない実装===
<source lang="c">
int gcd(int a,int b) {
if(a<=0 || b<=0)return 0;
while(b>0) {
int t=a%b;
a=b;
b=t;
}
return a;
}
</source>
===[[Haskell]]による実装===
<source lang="haskell">
gcd a b = if b<=0 then a else gcd b (mod a b)
</source>
==関連項目==
* [[最大公約数]]
* [[最小公倍数]]
