B. Divisor Subtraction
implementation; math; number theory
You are given an integer number \(n\). The following algorithm is applied to it: if \(n = 0\), then end algorithm; find the smallest prime divisor \(d\) of \(n\); 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.
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.