【ITニュース解説】Code optimization (Prime no.)

プログラムを作成する際、まず求められるのは要件通りに正しく動作することである。しかし、特にシステムエンジニアとしてのキャリアを考える上では、それに加えて「いかに効率的に動作するか」という視点が極めて重要になる。同じ結果を出すプログラムであっても、その処理方法、すなわちアルゴリズムの違いによって、実行にかかる時間が数秒から数時間にまで変わることも珍しくない。ここでは、古くからプログラミングの題材としてよく用いられる「素数判定」を例に、コードを段階的に最適化し、処理速度を向上させていくプロセスを解説する。素数とは、1とその数自身以外に正の約数を持たない、1より大きい自然数のことである。

ユーザーから入力された数値 n が素数かどうかを判定するプログラムを考えてみよう。最も直感的で分かりやすい方法は、素数の定義にそのまま従うことである。つまり、1から n までの全ての整数で n を順番に割っていき、割り切れた回数（約数の個数）を数えるのだ。もし約数の個数が2個（1と n 自身）だけであれば、その数 n は素数であると判定できる。この方法はロジックが単純で実装も容易だが、大きな問題を抱えている。それは、n の値が大きくなるにつれて、ループによる割り算の回数が比例して増加してしまう点だ。例えば n が100万であれば100万回、1億であれば1億回のループが必要になる。これでは、巨大な数を扱う場合に処理が完了するまで非常に長い時間がかかってしまい、実用的ではない。このように、処理時間が入力データのサイズに応じてどれだけ増えるかという指標を「時間計算量」と呼ぶが、この初歩的なアルゴリズムは時間計算量の観点から非効率的と言える。

最初の改善として、この無駄な計算を少しでも減らすことを考える。素数を判定する際、n が1と n 自身で割り切れるのは当たり前のことである。本当に知りたいのは、「2から n-1 までの範囲に、n を割り切る数が他に存在するかどうか」である。もしこの範囲に約数が一つでも見つかれば、その時点で n は素数ではないと確定する。逆に、一つも見つからなければ n は素数である。この考えに基づき、ループの範囲を1から n までではなく、2から n-1 までに狭めることができる。これにより、ループの回数を2回減らすことができる。これは確かに改善ではあるが、n が巨大な数である場合、全体から見れば微々たる差であり、根本的な解決には至らない。しかし、このように処理の前提条件を見直し、不要な計算を省こうとする思考プロセスが最適化の第一歩となる。

ここで、計算量を劇的に削減するための、より本質的な改善手法に目を向ける。それには、約数が持つ数学的な性質を利用する。ある数 n の約数を考えてみよう。例えば n が36の場合、その約数はペアで考えることができる。(1, 36), (2, 18), (3, 12), (4, 9), (6, 6) といった具合だ。ここで注目すべきは、ペアの一方の数が必ず n の平方根（この場合は√36 = 6）以下になっているという点である。これは偶然ではなく、全ての数で成り立つ普遍的な性質だ。もし n に√nより大きい約数 a が存在するとしたら、n = a * b を満たすペアの数 b は必ず√nより小さくなる。つまり、√nより大きい約数を探しに行かなくても、そのペアとなる√n以下の約数が必ず先に見つかるはずなのだ。この性質を利用すれば、n の約数を探す範囲は2から n まで、あるいは2から n-1 まで調べる必要はなく、2から√nまでで十分ということになる。もし2から√nまでの間に n を割り切る数が存在しなければ、それより大きい範囲にも約数は存在しないため、n は素数であると結論付けられる。これにより、ループの回数は n から√nへと大幅に削減される。例えば n が100万の場合、元の方法では約100万回のループが必要だったが、この方法なら√100万 = 1000回で済む。これは計算効率の飛躍的な向上である。実際のコードでは、計算コストのかかる平方根関数をループのたびに呼び出すのを避け、ループの継続条件を div <= sqrt(n) とする代わりに、両辺を2乗した div * div <= n と記述するのが一般的である。この方が整数演算のみで完結するため、より効率的だ。

アルゴリズムは平方根の利用で大幅に改善されたが、もう一段階、仕上げの最適化が可能だ。それは、素数でない数（合成数）を判定する場合の処理である。素数でない数は、2から√nまでの範囲に少なくとも一つの約数を持つ。そして重要なのは、その約数が一つでも見つかった瞬間に、その数が素数でないことは確定するということだ。したがって、それ以降のループ処理は全くの無駄となる。例えば99という数を判定する場合、最初に3で割り切れることが分かった時点で、99が素数でないことは確定する。その後に4, 5, 6...と√99（約9.9）まで調べ続ける必要はない。この考え方をコードに反映させるには、約数が見つかった（n % div == 0 が真になった）ブロックの中で、break 文を使って即座にループを強制的に終了させる。この改善は、特に偶数や3の倍数など、小さい数で割り切れる大きな合成数を判定する際に絶大な効果を発揮し、不要な計算を可能な限り排除することができる。このように、正しい結果を導くだけでなく、いかに無駄な処理を省き、効率的に答えにたどり着くかを考えることが、優れたプログラムを作成するための鍵となる。この一連の最適化プロセスは、あらゆるシステム開発において応用できる重要な思考法である。