問題一覧 > 通常問題

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

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

問題文

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

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

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

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

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

入力

L H

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

出力

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

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

サンプル

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

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

21=3―×7
22=2―×11
24=2―3×3
25=5―2
26=2―×13
27=3―3

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

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

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

25=5―2
26=2―×13
27=3―3
28=2―2×7
30=2―×3×5
32=2―5
33=3―×11
34=2―×17
35=5―×7

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

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

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

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

グロタンディーク素数。

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