問題一覧 > 通常問題

No.6 使いものにならないハッシュ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 345
作問者 : yuki2006yuki2006
1 ProblemId : 24 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:24

問題文

ハッシュに興味を持ったFrankは、ハッシュアルゴリズムに、このようなアルゴリズムを考えた。
自然数の各桁を足した合計、それも二桁以上になる場合は、それを繰り返す。
つまり、
hash(4)=4,
hash(17)=hash(1+7)=hash(8)=8,
hash(119)=hash(1+1+9)=hash(11)=hash(2)=2のようになる。

しかし実際使ってみるとコリジョン(計算値がかぶってしまうこと)が多く、あまり使い物にならなかった。

それでも諦めきれないFrankに対して、あなたは「落ち着け、素数を数えるんだ」と言った。
やけになったFrankは、自然数 \([K,N]\) (\(K \leq i \leq N\) の範囲ということ) の中の連続した素数列で上記のハッシュアルゴリズムを使用し、コリジョンが起こらない(値がかぶらない)最大の範囲を考えようとしている。
言った手前、申し訳なくなったあなたは、Frankの代わりに求めてあげることにした。

範囲\([K,N]\) (\(K \leq i \leq N\) の範囲)に含まれる連続した素数列で上記のハッシュアルゴリズムを使用した時に、
すべて異なる値になる最大の長さの素数列を求め、元の素数列の最初の素数を求めてください。
(複数同じ長さの素数列がある場合は、数が大きい方を選択する)

入力

\(K\)
\(N\)

\( 1 \leq K \leq N \)
\( 2 \leq N \leq 200000 \)
$[K,N]$の範囲に素数が含まれるのが保証されるものとする。

出力

数値を文字列で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
1
11
出力
3

まず\([1,11]\)の中に含まれる素数列は \( 2,3,5,7,11 \)である
Frankのハッシュアルゴリズムを適用すると \( 2,3,5,7,2 \)となる
ここでコリジョンが起こらない(値が重ならない)最大の長さの素数列を取り出すと\( 2,3,5,7 \) と\( 3,5,7,11 \)となる。
数が大きい方を選択するので素数列の最初は\(3\)となる。

サンプル2
入力
10
100
出力
31

\([10,100]\)の素数列を考えると以下の長さが最高となる
\( 31, 37, 41, 43, 47, 53 \rightarrow 4,1,5,7,2,8 \) 

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