No.308 素数は通れません

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 49
作問者 : matsu7874matsu7874
11 ProblemId : 840 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の1日目の問題として作られました。

問題文

このゲームはプレイヤーが1人で行う。
ゲームの目的はゲーム盤左上隅の1のマスからスタートし、以下の移動のルールを守りながら、Nのマスに到達することである。

移動のルール

  • 十字方向に隣接しているマスにのみ移動できる。
  • 素数の書かれたマスを通ってはならない。
2つの移動のルールを守って、1からNまで到達することができればプレイヤーの勝利である。

このゲームで使うゲーム盤は1からNの番号が順番に書かれたNマスで構成されている。
幅$W$高さ$\lfloor N/W \rfloor$のマスの塊の左下に、幅$N \mod{W}$高さ$1$のマスの塊がくっついた形をしている。
例としてN=9のとき、Wの値に応じて考えられるゲーム盤の一部を下に示す。

素数でない自然数Nが与えられます。
プレイヤーが勝利可能な最小の自然数Wを出力してください。

入力

N

$4 \le N \le 10^{24}$
$N$は素数でない。

出力

$W$
条件を満たす最小の$W$を一行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
9
出力
7

$N=9$のとき、$W=7$のゲーム盤がプレイヤーが勝利可能な最小の幅を持つゲーム盤である。

サンプル2
入力
4
出力
3

$W=3$が唯一のプレイヤーが勝利可能なゲーム盤です。 他の$N=4$のゲーム盤ではプレイヤーは素数のマスを通らずには1からNに到達する経路が存在しません。

サンプル3
入力
22
出力
7

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

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