整数に関する基本的なアルゴリズム
最大公約数と素数
続いて、二つの数値の最大公約数を求める、ユークリッドの互除法(ごじょほう)というアルゴリズムと、素数を求めるアルゴリズムである、エラトステネスのふるいを紹介します。
まず、最大公約数について説明します。数値mがnで割り切る時します。このとき、nはmの約数であると言います。具体的に言うと、4は2で割り切れるので、2は4の約数であると言えます。また、2つの数m1,m2があった時、nがその両方の約数であれば、nはm1とm2の公約数と言います。例をあげると、12と18の約数として、2と3があります。このような、公約数のうち、最大のものが最大公約数です。
続いて、素数について説明しましょう。素数とは、1と、その数自身(1は除く)しか、約数を持たない自然数のことを言います。例えば、5の約数は、1と5だけなので、素数であるといます。しかし、6は、2と3という約数を持つので、素数ではありません。ユークリッドの互除法とは、ある数までの範囲内にある、素数をすべて探し出すためのアルゴリズムです。以下、それらアルゴリズムを順を追って説明していきます。
ユークリッドの互除法
アルゴリズムの実装
ではまず、ユークリッドの互除法から説明していきましょう。アルゴリズムは前述のように非常にシンプルなものです。それを、より丁寧に記述すると、以下のようになります。ここでは、最大公約数を求めたい2つの整数を、m、nで、m>nであると仮定します。また、更に作業用の変数dを用意するものとします。
手順1. | 変数dにmとnの割り算の余りを代入する。 |
手順2. | dが0なら、nを最大公約数として出力する。 |
手順3. | mにnの値を代入する。 |
手順4. | nにdの値を代入する。 |
手順5. | 手順1に戻る。 |
これを、具体的な数値の例を出すと、以下のようになります。(図6-1.)この図から見ればわかるとおり、128と72の最大公約数は、16であることがわかります。

エラトステネスのふるい
エラトステネスのふるいとは
エラトステネスのふるいとは、ある自然数nまでの素数をすべて求めるための方法です。考え方は非常に単純で、1からnまでの数値の票を用意して、明らかに素数である2を残し、その倍数である、4,6,8,…を消していきます。それが終わると、2の次にある、消えていない数3が次の素数となるので、2の場合と同様に、その倍数である、6,9,12…などを消していきます。この要領で、次の素数5,7…で同様の処理を繰り返していくと、最終的に残った数値は、すべて素数になります(図6-2.)。これが、エラトステネスのふるいという考え方です。
図6-2.エラトステネスのふるい
用意するデータ構造
このアルゴリズムを実現するために、必要なデータ構造として、2つの配列を定義することにします。
一つ目として、要素数n+1の配列dataを用意します。これにより、N+1個の配列変数である、data[0],data[1],…,data[n]が得られます。
この配列には、初期状態として、すべて値1を代入しておくことにします。最終的に、処理が終わると、この番号に相当する数の要素の値が1であれば、その数は素数、そうでなければ、素数でないという判定を行うためにこの配列を用います。
二つ目として、素数の出力結果を格納する配列、resultを用意します。resultの大きさは、dataと同じく、N+1であるとします。なぜこの要素数となるかというと、出力される素数の数は不明ですが、dataの要素数を超えることがかに為、同じサイズの要素数であれば、確実に格納できるからです。一見無駄に見えますが、配列を使用し、その出力結果の数がわからないので、このようなサイズの配列を用意しておくことにします。この配列には、dataで得られた素数を入れておくものとします。
アルゴリズムの手順
では、具体的なアルゴリズムの手順を見てみることにしましょう。
手順1. | 変数mを用意し、2を代入する。(この変数は、配列dataにアクセスするためのもの) |
手順2. | 変数nを用意し、0を代入する。(この変数は、配列resultにアクセスするためのもの) |
手順3. | 配列dataの値を全てすべて1で初期化する。 |
手順4. | 配列resultの値を全てすべて0で初期化する。 |
手順5. | data[0]、data[1]に、0を代入する。(あらじめ素数でない数は排除する) |
手順6. | 変数iを用意し、iに2×mを代入する。 |
手順7. | iがN未満の間、data[i]に、0を代入し、iにmを足すという処理を繰り返す。 |
手順8. | result[n]にmを代入する。 |
手順9. | nをインクリメントする。 |
手順10. | mをインクリメントする。 |
手順11. | mがNより大きくなったら、手順13へ。 |
手順12. | data[m]が1ならば、手順6へ。 |
手順13. | resultの値を出力し、処理を終了する。 |
処理が若干複雑になっていまいましたが、このイメージを図に表わすと、以下のようになります。(図6-3.)
図6-3.エラトステネスのふるいのアルゴリズム