解説


この問題では、答えの候補を全探索することで解くことが出来ます。

素数 と正整数 について、
以上 以下の整数の中に、 の倍数が存在するか」・・・(★)
という判定を行います。
の倍数が存在する場合、 と表せる数が 以上 以下の中に存在することになるため、
は答えの候補になります。
素数 と正整数 を全探索し、(★) を満たすような の最大値が答えになります。

一般に、 以下の正整数のうち の倍数の個数は と計算できるため、
(★)の判定は  かどうかと同値であり、これは で求められます。

また、 という条件より、 以上 以下の整数の中に、 の倍数が必ず存在するため、答えの下限は になります。
よって、調べる の範囲は 以上で良く、 調べる素数 も  となる範囲のみを調べれば良いです。

調べる必要がある の最大値は 、調べる必要がある素数 の最大値は であり、全探索が十分間に合います。