No.371

$L \leq p^2 \leq H$ ($p$ は素数) となる $p$ があれば, その中の最大の素数が最小の素因数になる数を探す.

そうでない場合は $[L, H]$ の最小の素因数が最大になる数を求める. エラトステネスの篩を改造して, $[L, H]$ 間の最小の素因数を更新していくやり方が速い.

どちらの場合も探索範囲は高々 $(p+a)^2 - p^2 = 2pa + a^2$ ($a$ は $p$ の次の素数との差) であり, $p \leq 10^5$ の範囲での $a$ の最大値を計算すると $72$ であるので, なんとか間に合う.