2 Keys Keyboard

면접 대비

시간 제한1초메모리 제한1024 MB

요약

화면에 A가 하나 있는 상태에서 전체 복사와 붙여넣기만 사용해 정확히 N개의 A를 만드는 최소 연산 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 수학, 그리디, 정수론
정답자: 아직 제출이 없습니다

문제

Imagine a very simple text editor that supports exactly two operations:

Copy All : Copy the entire current screen content into the clipboard. (Partial copy is not allowed.)
Paste : Paste the content from the clipboard onto the screen.

Initially, the screen contains a single character A. Your goal is to display exactly $N$ characters A on the screen using the minimum number of operations possible. Find the minimum number of operations required when acting optimally.

입력

The first line contains a single integer $N$ , representing the number of characters A to be displayed. $(1 \leq N \leq 1\\,000\\,000)$

출력

Print a single integer: the minimum number of operations required.

예제2

예제 1
입력
```
9
```
예상 출력
```
6
```
예제 2
입력
```
1
```
예상 출력
```
0
```