プログラムというよりアルゴリズム？

　注目URLでちょっと話題の、このJeffさんは、いつもやや極論によって物議を醸すネタ師的なところがある。

どうしてプログラマに・・・プログラムが書けないのか?

ここでプログラマに試されている問題とは以下のものである。

1から100までの数をプリントするプログラムを書け。ただし3の倍数のとき
は数の代わりに｢Fizz｣と、5の倍数のときは｢Buzz｣とプリントし、3と5両方
の倍数の場合には｢FizzBuzz｣とプリントすること。

面接時に、2分以内でこのプログラミングができない応募者が200人中199人だと嘆く。問題の内容はともかく、自分は常々プログラミングの世界は100人の凡庸なプログラマより１人の天才が必要な世界だと思っているので、特に驚くには当たらない。著者のところでは、その1人の天才を求人しようとしているのだとしたら、当然の話ではある。

　さて、この面接の問題だが、腕に覚えのあるいろいろな人が挑戦しているようだ。動くだけのプログラムだけならどうやってもできそうだが、問うているポイントはどこにあるのかはっきりしない。コンパクトで美しいプログラムを直感的に書けるかどうかだけなのだろうか。

　ちょっと考えると、3か5で割り切れるどうかの判定に加え、さらに15でも割り切れないかどうかの判定もしなければならないことがわかる。コンパクトに書くには、判定の順序を先に15で割り切れるかどうかを先に行い、そうでない数値に対してのみ3か5で割り切れる判定にする。つまり

15で割り切れる→　yes　→次の数の判定へ
3で割り切れる→　yes　→次の数の判定へ
5で割り切れる→　yes　→次の数の判定へ

という順で、1から100までの数について繰り返す。
　一見これでよさそうに思えるが、本当にそうだろうか。割り切れる判定をする順序によって、比較の回数がどう異なるか数えてみる。

• 15→3→5の順に判定する場合

除数	比較回数	倍数の個数
15	100回	6個
3	100-6=94回	27個
5	100-33=67回	14個
総計	261回

• 3→15→5の順に判定する場合

除数	比較回数	倍数の個数
3	100回	33個
15	33回	6個
5	100-33=67回	14個
総計	200回

　15の倍数は3の倍数の33個だけの判定をすればよいので、判定順序を変えただけで、全体の判定回数を減らすことができそうだ。どこか間違っているだろうか？
　データ数が膨大になれば、データがランダムな数値の列であれば判定の効率も何もないが、連続した数値であれば判定順序が大きく影響する場合もある。

　自称アルゴリズム屋としては、「美しいプログラム」を書くことよりも、本当に効率がよいのかの方が気になる。