\(3N\) 以下の素数はあらかじめ計算しておく.

\(a+b+c=d\) とすると, \(b+c=d-a\) となる.

\(b\) を固定して \(b+c=x\) となる組み合わせの数 \(A(x)\) を \(b \lt c \leq N\) の範囲で全探索で求める. また \(d-a=x\) となる組み合わせの数 \(B(x)\) を \(a \lt b\) の範囲で全探索で求める. そして \(\sum A(x)B(x)\) が \(b\) を固定したときに \(a+b+c\) が素数となる組み合わせの数となる.

\(b\) を増やすと次に \(d-a = x\) となる組み合わせの数は直前の \(b\) を \(a\) としたものだけ足せばいいので, 計算量を削減できる.