No.371 ぼく悪いプライムじゃないよ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : maimai / テスター : 🍡yurahuna🍡yurahuna

6 ProblemId : 980 / 出題時の順位表

問題文

437「ぷるぷる、ぼくわるいプライムじゃないよ」

試しに437を19で割ってみると23となり、割り切れることが確認できます。
どうやら彼は素数(prime number)では無かったようです。

もしかしたら、他にも素数と間違われている合成数があるかもしれません。

$L$以上$H$以下の範囲の整数について、最も素数と間違えそうな合成数を求めてください。

ただし、「最も素数と間違えそうな合成数」とは、 「最小の素因数」が最大である合成数とします。
例えば、$28 = 2^2 \times 7$の最小の素因数は2です。

入力

L H

$(3 \le L < H \le 10^{10})$
を満たす$L$と$H$がスペース区切りで与えられます。
$10^{10}$は、32bit整数で表現できない値です。

出力

$L$以上$H$以下の範囲に存在する合成数の最小の素因数を求めたとき、 それが最大になるような値を1つ出力してください。
そのような値が複数存在する場合、元の整数が最も大きいものを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
21 27
出力
25

21から27までの合成数をすべて素因数分解してみます。

$21 = \underline{3} \times 7$
$22 = \underline{2} \times 11$
$24 = \underline{2}^3 \times 3$
$25 = \underline{5}^2$
$26 = \underline{2} \times 13$
$27 = \underline{3}^3$

最小の素因数は、下線を引いた数字になります。
下線を引いた数字$3,2,5$の中で最大の数字は$5$なので、それに対応する25を出力します。

サンプル2
入力
25 35
出力
35

25から35までの合成数をすべて素因数分解してみます。

$25 = \underline{5}^2$
$26 = \underline{2} \times 13$
$27 = \underline{3}^3$
$28 = \underline{2}^2 \times 7$
$30 = \underline{2} \times 3 \times 5$
$32 = \underline{2}^5$
$33 = \underline{3} \times 11$
$34 = \underline{2} \times 17$
$35 = \underline{5} \times 7$

最小の素因数は、下線を引いた数字になります。
下線を引いた数字$3,2,5$の中で最大の数字は$5$ですが、それに対応する数は25と35があります。
複数存在する場合は最大の整数を選択します。よって、35を出力します。

サンプル3
入力
150 151
出力
150

範囲内の合成数は150のみ。

サンプル4
入力
56 62
出力
57

グロタンディーク素数。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。