アルゴリズムを使って数学の問題を解く
山崎講師アルゴリズムを使って数学の問題を解くことができます。アルゴリズムを使用することで、正確で信頼性の高い計算結果を得ることができます。
ここでは最大公約数を求めるユークリッドの互除法と素数を求めるエラトステネスの篩をご紹介します。
ユークリッドの互除法
問題：2つの正の整数aとbの最大公約数【Greatest Common Divisor:GCD】を見つけます。
※ユークリッド（Euclid）は、古代ギリシャの数学者であり、幾何学や数論などの分野で重要な貢献をした人物です。彼は紀元前300年頃に活動し、その業績は数学史上において大きな影響力を持っています。
この問題を解決するためには、ユークリッドの互除法と呼ばれるアルゴリズムが有効です。ユークリッドの互除法は、以下の手順で実行されます。
- aをbで割り、余りrを取得します。
- rが0でない場合、bをrにaをbに置き換え、1に戻ります。
- rが0の場合、bが最大公約数です。
例えば、a=24, b=16の場合、以下のようになります。
- 24を16で割ると、余りは8になります。
- 8が0でないので、bを8にaを16に置き換え、1に戻ります。
- 16を8で割ると、余りは0になります。したがって、最大公約数は8です。
| ＜ユークリッドの互除法の図を使った説明＞ |
＜サンプルプログラム＞
＜出力結果＞
| GCD of 24 and 16 is 8 |
練習問題1
以下の流れ図の読み方を講師から教わり、次の練習問題でJavaとして実装しなさい。
基本情報技術者試験 平成31年春期 午前問7
練習問題2
割り算ではなく引き算で実現するユークリッドの互除法のJavaプログラムを作成してください。
エラトステネスの篩
エラトステネスの篩は、素数を見つけるための古典的なアルゴリズムです。
※エラトステネスは、紀元前3世紀の数学者・地理学者であり、多岐にわたる分野で活躍しました。地中海にある2つの都市（アレクサンドリアとシラクサ）の間の距離を測定し、地球の円周を推定したという逸話を聞いたことのある方もいるでしょう。
素数とは、1と自分自身以外の正の約数を持たない自然数です。なお、1は素数ではありません。
このアルゴリズムは、以下の手順で実行されます。
- 0からnまでのすべての自然数をリストアップする。
- 0と１は素数ではないのでリストから削除する。
- 最初の数2を素数とし、その倍数を素数リストから削除する。
- 次に残った数の最初の数を素数とし、その倍数をリストから削除する。
- 手順2と3を繰り返す。
- リストに残った数は、素数です。
たとえば、nが30の場合、以下のようになります。
- 0から30までの自然数をリストアップする。
- 0と１は素数ではないのでリストから削除する。
- 最初の数2を素数とし、その倍数をリストから削除する。
- 残った数の最初の数3を素数とし、その倍数をリストから削除する。
- 手順2と3を繰り返す。
- リストに残った数は素数。
このように、エラトステネスの篩は、非常にシンプルなアルゴリズムであり、効率的に素数を見つけることができます。
※19行目でfor文の継続条件式が「 i * i < digits.length 」となっているのは、p * p より小さい倍数は既に他の素数の倍数としてふるい落とされているためです。例えば30までの素数であれば、7*7＝49で30を超えます。5より大きい素数の倍数は既にふるい落とされているので処理は不要なのです。
| ＜エラトステネスの篩を自分の手で検証する＞ |
＜サンプルプログラム＞
＜出力結果の例＞
| いくつまでの素数を知りたいですか？: 30 2 3 5 7 11 13 17 19 23 29 |
