1076B.md (903B)
1 Source: https://codeforces.com/problemset/problem/1076/B 2 3 B. Divisor Subtraction 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an integer number $n$. The following algorithm is applied to it: 22 23 1. if $n = 0$, then end algorithm; 24 2. find the smallest prime divisor $d$ of $n$; 25 3. subtract $d$ from $n$ and go to step $1$. 26 27 Determine the number of subtrations the algorithm will make. 28 29 Input 30 31 The only line contains a single integer $n$ ($2 \le n \le 10^{10}$). 32 33 Output 34 35 Print a single integer — the number of subtractions the algorithm will make. 36 37 Examples 38 39 Input 40 41 ``` 42 5 43 ``` 44 45 Output 46 47 ``` 48 1 49 ``` 50 51 Input 52 53 ``` 54 4 55 ``` 56 57 Output 58 59 ``` 60 2 61 ``` 62 63 Note 64 65 In the first example $5$ is the smallest prime divisor, thus it gets subtracted right away to make a $0$. 66 67 In the second example $2$ is the smallest prime divisor at both steps.