D言語で素数列を求めるコードを書いてみた
ことの由来
Haskellの練習がしたくて、Sphere Online Judgeで競技プログラミング始めてみたのである。関数型言語はどっちかというと競技プログラミングの方が強そうな気がしたので。
初っ端から素数の問題にぶちあたり、Haskellで素数どうやって書いたもんかと色々試行錯誤した結果、手続き型言語の方が簡単であるという結論に達し、C++を使おうと思い立った。(この辺りで最初の目的が失われている)
ところがSPOJはC++は0xが使えないという大変に寂しい状況であり、いっそDでも使ってみるかーとか思ったのが始まり。
問題設定
という訳で問題は以下。
http://www.spoj.pl/problems/PRIME1/
入力の範囲の素数を求めて出力せよ、という問題である。まぁ難しくはないが、それ故に速度は拘りたいので、Ruby・Pythonには遠慮してもらう。(というか今見ると数値上限が厳しいのでRuby・Pythonの標準環境だと無理かもしれない)
Dのコード
書いてみたのが以下。
基本的には篩で求めるのだが、あまりにデカいものを篩でいちいち求めるのは無駄が多いので、一定を越えたものに関しては逐一求めるようにした。
999900000〜1000000000の素数列を求めるようなケースが1秒で実行できることを確認したので、まぁ遅くは無い筈。
バグとかアドバイス等ありましたら御気軽にどうぞ。その方が勉強になって助かります。
ちなみに
SPOJにコミットしようとしたらstd.algorithmなんて無いよ!とか言われたのでちゃぶ台引っくり返してる所。