最終更新日：2026年8月27日

fe fe-technology algorithm trace

まず結論

ユークリッドの互除法とは、2つの整数の最大公約数を、値をだんだん小さくしながら求めるアルゴリズムです。

基本情報技術者試験では、互除法そのものを覚えるだけでなく、フローチャートや疑似言語を読んで、変数の値を1回ずつ追跡する力が重要です。

特に比較回数を問われたら、次の3点を意識します。

  • 比較する前の値を確認する
  • 分岐後に更新された値で、次の比較へ進む
  • 終了するときの等号判定も比較1回に含める

直感的な説明

2つの長さから、どちらにもぴったり入る最大の共通単位を探すイメージです。

例えば、長い方から短い方を何度も引きます。

L > S なら
L = L - S

L < S なら
S = S - L

L = S になったら終了

大きい方を小さくしていくと、やがて2つの値が同じになります。

その同じ値が最大公約数です。

48 と 18

48 - 18 = 30
30 - 18 = 12
18 - 12 = 6
12 - 6  = 6

6 = 6
→ 最大公約数は6

ポイントは、毎回「どちらが大きいか」を見て、大きい方だけを更新することです。

定義・仕組み

最大公約数とは、2つ以上の整数をどちらも割り切れる整数のうち、最大のものです。

ユークリッドの互除法では、2つの整数の関係を保ったまま値を小さくしていきます。

引き算を使う形

フローチャートでは、次のような形で表されることがあります。

L > S → L = L - S
L < S → S = S - L
L = S → 終了

この方法は、処理の流れを追いやすいため、フローチャート問題と相性がよい形です。

余りを使う形

一般的には、余りを使って次のように計算する方法もよく使われます。

A ÷ B の余りを R とする
A = B
B = R

B = 0 になるまで繰り返す

例えば、48と18なら、

48 ÷ 18 → 余り12
18 ÷ 12 → 余り6
12 ÷ 6  → 余り0

したがって最大公約数は6です。

引き算型と余り型は書き方が違いますが、どちらも大きな値を小さくしながら最大公約数へ近づくという考え方は同じです。

公式の出題範囲やシラバスは、IPA：基本情報技術者試験 から確認できます。

科目Aでどう出る？

科目Aでは、アルゴリズムの処理結果や比較回数を問う形で出ることがあります。

このとき、暗算だけで追うより、比較ごとの値を表に書く方が安全です。

例えば、次の初期値を考えます。

L = 30
S = 18
比較回数 比較前のL 比較前のS 判定 更新後
1 30 18 L > S L = 12
2 12 18 L < S S = 6
3 12 6 L > S L = 6
4 6 6 L = S 終了

この場合、比較回数は4回です。

最後の L = S は値を更新しませんが、比較そのものは行っているため1回に数えます。

科目Bでどう使う？

このテーマは、科目Bのトレース練習にも向いています。

科目Bでは、処理を頭の中だけで追うと、値の更新場所を見失いやすくなります。

次の順番で追うと安定します。

  1. 初期値を書く
  2. 条件を判定する
  3. 実行された処理だけ反映する
  4. 更新後の値を次の行へ写す
  5. 終了条件を満たすまで繰り返す

特に大切なのは、分岐の両方を実行しないことです。

L > S なら L だけ更新
L < S なら S だけ更新

フローチャートや疑似言語のトレースでは、この「どの処理を通ったか」を1行ずつ記録する習慣が役立ちます。

探索アルゴリズムでも同じように変数を追うので、二分探索の記事も合わせて読むと、トレースの練習を広げられます。

どんな場面で使う？

ユークリッドの互除法は、最大公約数を求めたいときに使います。

最大公約数は、例えば次のような場面で関係します。

  • 分数を約分する
  • 複数の長さを同じ大きさで区切る
  • 周期や繰返しの単位を整理する
  • 整数を扱うアルゴリズムの基礎を学ぶ

FE対策では、実務利用を細かく覚えるより、繰返し処理と条件分岐を正確に追えることを優先します。

よくある誤解・混同

最後の等号判定を数えない

比較回数を問われたときに最も注意したい点です。

L = S
→ 処理終了

ここでも条件判定を1回行っています。

したがって、終了時の比較も回数に含めます。

更新後の値を使わずに次へ進む

例えば、

L = 30
S = 18

30 > 18
→ L = 12

となったら、次の比較は 30 と 18 ではなく、12と18です。

トレース表には、更新後の値を必ず次の行へ移します。

大きい方と小さい方を固定だと思う

最初に大きかった変数が、ずっと大きいとは限りません。

30 > 18
→ L = 12

次は
12 < 18

このように大小関係は途中で入れ替わります。

変数名ではなく、その時点の値を比較することが重要です。

引き算型と余り型は別のアルゴリズムだと思う

処理の書き方は違いますが、どちらもユークリッドの互除法の考え方です。

FEでは、問題文やフローチャートに書かれた処理をそのまま追い、勝手に別の方法へ置き換えないようにします。

まとめ（試験直前用）

  • ユークリッドの互除法は、2数の最大公約数を求めるアルゴリズム
  • 引き算型では、大きい方から小さい方を引く
  • 余り型では、除算の余りを使って値を小さくする
  • フローチャートでは、比較ごとに変数の値を記録する
  • 更新後の値で次の比較を行う
  • 終了時の等号判定も比較1回に含める
  • 科目Bでは、条件分岐と変数更新を1行ずつ追う

© 2024-2026 stemtazoo. All rights reserved.