最近何もかいてないし、今日のtopcoderのdiv2 mediumでだめだったので。
2^16と2^32までに出てくる素数の数をそれぞれ求めたことがあったので、
今更それをネタにします。既出なお話ですけどね。
2〜65536(2^16)までに素数は6,542個ある
2〜4294967296(2^32)までに素数は203,280,221個ある
素数の求めかた
nが素数であるかを求めるとき、2〜n-1までの値で割り切れないことを試すが、
2で割り切れなければ、4,6,8...といった偶数では割り切れないので、開始値は3からで2づつ増加させて試すのが一番実装が簡単である。
しかしそれでも、9,15,21...など3で割り切れる値もそこそこあるため、無駄な計算が入ってしまう。
そこで、既に判定した素数の集合（2,3,5,7,11...）で割り切れなかったらそれは素数という実装にすることで、
上に挙げた無駄な計算がなくなる。
また、例えば23の素数を求める際、5より大きい素数以降では割り切れないので素数といえる。
他に119は7で割り切れるため素数ではないが、11より大きい素数が来る前で割り切れる。
つまり、求めたい数の平方根(√n)に最も近い小さい素数まで判定したのであれば、それは割り切れなかったと判断し計算を切り上げ、素数と判断することで、計算量をさらに減らすことが出来る。
実際には平方根を求めるのは時間がかかる処理なので、
値nがある素数mで割り切れなかった、かつ、値nをmの2乗を上回っていたら値nは素数である、と判定する。
（√n=m なので n=m^2であるが、この計算は後者のほうが数倍速い。）
また、このことからこの場合2から4294967296までの素数を探索したいので、√4294967296=65536までの素数6,542個を算出しておけば、後はこの6,542個の素数で割り切れるかで素数か否かを判定できる。
