No.308 素数は通れません

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / タグ : / 解いたユーザー数 42
作問者 : matsu7874

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

提出ページヘ