Triple Primes [yukicoder No.843] - はまやんはまやんはまやん

前提知識

素数列挙

あるといい知識

素数定理

解説

以下の実装では関数として隠蔽してしまっているが、
makePrimes(N) := [2,N]の素数の集合を返す
makePrimesBool(N) := [2,N]の素数であればtrueが入っているbool配列を返す
というのをエラトステネスの篩を元に実装している。
これがまず前提として理解している（またはライブラリを持ってるでもいいけど）必要がある。
　
全探索対象を探そう。
全探索できそうな対象の幅を見てみよう。
p,qはN通り試す必要がある。
だが、rは2乗になっているので、p+q≦2Nであることを考えると、sqrt(2N)まで試せば良さそうである。
かつ、2つ確定するともう1つも確定するので、p,rを全探索することで全通り試せそうである。
これでO(Nsqrt(N))であり、ちょっと心配だが、p,rの全探索対象を素数に限定して、
qの素数判定も予め素数かどうかのテーブルを作っておいて判定するようにすれば通る。
　
あと、備考であるが、素数定理というのもあり、N以下の素数の個数は近似N/logNであることを使えば、
素数だけ判定するようにすれば、まあまあ早くなることが断定できる。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	M = sqrt(2 * N) + 5;

	auto vp_n = makePrimes(N);
	auto vp_m = makePrimes(M);
	auto vpb_n = makePrimesBool(N);

	int ans = 0;
	fore(p, vp_n) fore(r, vp_m) if(p <= N and r <= N) {
		int q = r * r - p;
		if (0 <= q and vpb_n[q] and q <= N) ans++;
	}
	cout << ans << endl;
}