【アルゴリズム】古代ギリシャから続く最古の計算手法！「ユークリッドの互除法」｜情報処理問題1000本ノック
基本情報技術者・応用情報技術者試験の数値計算・アルゴリズム分野で頻出の古典的アルゴリズム。「ユークリッドの互除法」の定義と、選択肢に登場する他の数学的アルゴリズムとの違いを攻略しましょう。
1. 【 問題 】：テクノロジ系（アルゴリズム・数値計算）
【 問題 】 2つの整数の最大公約数（GCD：Greatest Common Divisor）を、割り算（余りを求める計算）を繰り返すことによって効率的に求めるアルゴリズムとして知られているものは、次のうちどれか。
（ア）ユークリッドの互除法
（イ）エラトステネスの篩（ふるい）
（ウ）ニュートン法
（エ）モンテカルロ法
2. 正解：
正解：（ア）ユークリッドの互除法
3. 解説：「『余りで割る』を余りが0になるまで繰り返す！」
ユークリッドの互除法は、「2つの自然数 $a$ と $b$（$a > b$）の最大公約数は、$b$ と『$a$ を $b$ で割った余り $r$』の最大公約数と等しい」という性質を利用して、余りが0になるまで割り算を繰り返す計算手法です。
【問題選択肢（数学的アルゴリズム）の正体一覧】 ← 超頻出ポイント！
| アルゴリズム名 | 概要・何を求めるものか |
|---|---|
| （ア）ユークリッドの互除法 | 2つの整数の「最大公約数（GCD）」を求める。 |
| （イ）エラトステネスの篩（ふるい） | 指定した範囲の全自然数から「素数」を抽出・列挙する。 |
| （ウ）ニュートン法 | 方程式の「近似解（ルートの値など）」を収束させて求める。 |
| （エ）モンテカルロ法 | 「乱数（確率）」を多数発生させて数値計算・近似解（円周率など）を求める。 |
1. 理解のコツ（ユークリッドの互除法の手順例：1071 と 102 の最大公約数）:
① $1071 \div 102 = 10$ 余り 51
② $102 \div 51 = 2$ 余り 0 ➔ 余りが0になった時の割った数「51」が最大公約数！
2. 試験対策の視点: プログラミングやアルゴリズムの基本問題で非常に頻出です。
問題文に「最大公約数」「あまりを求める」「互いに割る」と出たらユークリッドの互除法、「素数を探す」と出たらエラトステネスの篩を選択しましょう！
4. まとめ
2つの整数の最大公約数を求める最古・最重要なアルゴリズム。これがユークリッドの互除法です。素数を見つける「エラトステネスの篩」や近似解を求める「ニュートン法」との言葉の区別も完璧にしておきましょう！
PR