TAKESAKO @ Yet another Cybozu Labs

キミならどう書く 2.0 - ROUND 1 -

LL Ring の前哨戦として「キミならどう書く 2.0」の開催です！
お題は「100までの整数から素数を列挙せよ」です．

ということで、世界最小のコンパイラ/インタプリタと言われている
Brainf*ckで1～100までの素数を列挙してみました。

ちなみに brainf*ck で prgramming するのは今回が初めてです。

Wikipedia日本語版の解説より

開発者Urban Müllerがコンパイラがなるべく小さくなる言語として考案した。実際、Muellerが開発したコンパイラのサイズは123バイト(キロバイトではない!)、インタプリタは98バイトしかない。また、実行可能な命令はわずか8つしかない。

処理系には十分なサイズのbyte型配列とその要素のひとつを指すポインタがある。ポインタを「>」「<」命令で移動させながら、そのポインタが指す値を増減させて処理を進めていく。 これだけでチューリングマシンで実行可能なあらゆるプログラムが記述できるとされている。

Brainf*ckの言語仕様は非常に単純で、

1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。
3. + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
4. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
5. . ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。
6. , 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。
7. [ ポインタが指す値が0なら、対応する ] までジャンプする。C言語の「while(!*ptr){」に相当。
8. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

ね、簡単でしょ？

素数の列挙には lookup table という超高速なアルゴリズムを採用しています。:-)

Brainf*ckではbyte型の配列つまり0～255の整数しか扱えないため、256以上の素数を真面目に計算しようとすると多倍長演算をサポートしないといけません。ふつうの中学生は素因数分解の問題を解くのに100までの素数は大体暗記してるでしょ、ということで、実は lookup table という手法は現実世界に近い解なのです。

じゃあ、100以上の素数を列挙したい場合はどうすればいいのか？という素朴な疑問に
お答えするため、ppencode ならぬ bpencode なるものをさらに作ってみました。

bpencode - Brainf*ck Prime Encode for JavaScript

ブラウザ上で brainf*ck のプログラミングの様子を動作確認できます。

上のデモ画面では、300までの素数を表示する brainf*ck のプログラムを動的に生成しています。
ブラウザでの計算速度の限界があるため、今のところ5桁の数字99999まで対応しています。

どうぞご利用ください。