Divisor Subtraction

###### 题目描述 给定一个整数$n$，按照如下算法进行操作 1. 如果$n=0$，结束算法； 1. 找到$n$的最小质因子$d$； 1. $n-=d$并回到操作$1$ ###### 输入格式 一行一个整数$n(2\leq n\leq 10^{10})$ ###### 输出格式 输出一个整数——该算法进行循环操作的次数

You are given an integer number $ n $ . The following algorithm is applied to it: 1. if $ n = 0 $ , then end algorithm; 2. find the smallest prime divisor $ d $ of $ n $ ; 3. subtract $ d $ from $ n $ and go to step $ 1 $ . Determine the number of subtrations the algorithm will make.

The only line contains a single integer $ n $ ( $ 2 \le n \le 10^{10} $ ).

Print a single integer — the number of subtractions the algorithm will make.

5

1

4

2

In the first example $ 5 $ is the smallest prime divisor, thus it gets subtracted right away to make a $ 0 $ . In the second example $ 2 $ is the smallest prime divisor at both steps.