問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 : maimai / テスター : 🍡yurahuna🍡yurahuna
8 ProblemId : 980 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 19:42:00

問題文

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

グロタンディーク素数。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。