No.308 Primes Cannot Be Passed
レベル :
/ AI推定難易度 : 2250
/ 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 :
matsu7874
タグ : / 解いたユーザー数 61
作問者 :
matsu7874
問題文最終更新日: 2026-06-25 04:07:10
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2015
(順位表)
の他の問題:
Note
This problem was created as the problem for day 1 of the Advent Calendar Contest Advent Calendar 2015.Problem Statement
This game is played by a single player.
The goal of the game is to start from the cell 1 at the top-left corner of the game board and reach the cell N while following the movement rules below.
Movement rules
- You can only move to a cell adjacent in one of the four directions (up, down, left, right).
- You must not pass through a cell with a prime number written on it.
The game board used in this game consists of N cells on which the numbers from 1 to N are written in order.
Its shape is a block of cells of width $W$ and height $\lfloor N/W \rfloor$, with a block of cells of width $N \mod{W}$ and height $1$ attached to its bottom left.
As an example, some of the possible game boards for N=9, depending on the value of W, are shown below.
You are given a natural number N that is not prime.
Output the smallest natural number W for which the player can win.
Input
N
$4 \le N \le 10^{24}$
$N$ is not prime.
Output
$W$
Output the smallest $W$ satisfying the condition on one line. Print a newline at the end.
Sample
Sample 1
Input
9
Output
7
When $N=9$, the game board with $W=7$ is the game board with the smallest width on which the player can win.
Sample 2
Input
4
Output
3
$W=3$ is the only game board on which the player can win. On the other game boards with $N=4$, there is no path from 1 to N that lets the player avoid passing through prime cells.
Sample 3
Input
22
Output
7
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。