「ユークリッドの互除法」を編集中
ナビゲーションに移動
検索に移動
この編集を取り消せます。 下記の差分を確認して、本当に取り消していいか検証してください。よろしければ変更を保存して取り消しを完了してください。
| 最新版 | 編集中の文章 | ||
| 1行目: | 1行目: | ||
| − | '''ユークリッドの互除法''' | + | '''ユークリッドの互除法'''とは、2個の正の[[整数]]の[[最大公約数]]を比較的高速に求める[[アルゴリズム]]である。 |
==実装例== | ==実装例== | ||
| − | === | + | ===シンプルな実装=== |
| − | |||
<source lang="c"> | <source lang="c"> | ||
| − | int gcd(int a, int b) { | + | int gcd(int a,int b) { |
| − | + | return b==0?a:gcd(b,a%b); | |
} | } | ||
</source> | </source> | ||
| − | + | ===再帰を使わない実装=== | |
<source lang="c"> | <source lang="c"> | ||
| − | int gcd(int a, int b) { | + | 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> | </source> | ||
| − | === | + | ===[[Haskell]]による実装=== |
| − | [[Haskell]] | ||
<source lang="haskell"> | <source lang="haskell"> | ||
gcd a b = if b<=0 then a else gcd b (mod a b) | gcd a b = if b<=0 then a else gcd b (mod a b) | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</source> | </source> | ||
| 52行目: | 30行目: | ||
* [[最大公約数]] | * [[最大公約数]] | ||
* [[最小公倍数]] | * [[最小公倍数]] | ||
| − | |||
| − | |||
| − | |||
