No.371 ぼく悪いプライムじゃないよ
タグ : / 解いたユーザー数 87
作問者 :
🍡yurahuna
問題文
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
入力
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
グロタンディーク素数。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。