No.1737 One to N
タグ : / 解いたユーザー数 229
作問者 :
Shirotsume
/ テスター :
nok0
とりゐ
Problem Statement
You have an integer $X$. Initially, $X = 1$.
You may perform the following operation on the integer $X$ any number of times, possibly $0$ times.
Operation: Choose $1$ integer that is at least $2$, and let $K$ be the chosen integer. Pay $K$ yen and replace $X$ with $KX$.
Given a positive integer $N$, find the minimum amount of money required to make $X = N$.
Constraints
- $ 1 \leq N \leq 3 \times 10^5$
- $N$ is an integer.
Input
The input is given from Standard Input in the following format.$N$
Output
Output the minimum amount of money required. Print a newline at the end.
Sample
Sample 1
Input
12
Output
7
Initially, $X = 1$. If you choose $K = 3$ in the $1$st operation, you pay $3$ yen and $X$ is replaced with $3 \times 1 = 3$.
If you choose $K = 4$ in the $2$nd operation, you pay $4$ yen and $X$ is replaced with $4 \times 3 = 12$.
With the above procedure, you can make $X = N$ by paying a total of $7$ yen. There is no procedure that makes $X = N$ for less than $7$ yen, so output $7$.
Sample 2
Input
123456
Output
658
Sample 3
Input
1
Output
0
Since $X = 1$ from the start, you do not need to pay any money.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。