No.308 素数は通れません
matsu7874問題文最終更新日: 2017-05-10 22:36:03
問題文
このゲームはプレイヤーが1人で行う。
ゲームの目的はゲーム盤左上隅の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$のゲーム盤ではプレイヤーは素数のマスを通らずには１からNに到達する経路が存在しません。
サンプル3
入力
22
出力
7
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。