873さんのを取り入れた結果（VCでコンパイル）
１億　1.859sec
１０億　23.5sec

いまいち自分の実力が分からんから
前にやってた人と環境をあわせようと思って
cygwin g++ -O3でコンパイルしたら
１億　1.281sec
１０億　17.859sec
（ただしファイル出力はバイナリ）

VCで最適化かけたほうが速いもんだと思ってたんだけど…そういうわけじゃないのね