問題
atcoder.jp
提出解答
atcoder.jp
問題の概要
次を見たす整数
の数を求めよ.
制約
解法
以上
以下の整数
が
となる素数
に対して,
と表されるとき,
であるから,
となる.
よって,
となる各素数の組
に対して,
となる素数
の数を高速に計算できれば良い.
これは
を
以下の素数とすると,
である.
ここで,
は
の範囲まで求めれば良く, これはエラトステネスの篩を利用することで
時間で求められる.
また, 調べるべき
の数は高々
組である.
以上から,
時間で求めることができた