Divisor Subtraction (Codeforces 1076B)
Tags: Implement, 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.

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

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

Note: 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.

Sample Inputs:
5

4

Sample Outputs:
1

2

Solution (Python):
def minPrime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return i
    return False
n = int(input())
if n % 2 == 0:
    print(n // 2)
else:
    m = minPrime(n)
    if not m:
        print(1)
    else:
        print(1 + (n - m) // 2)

Solution (Python):
from math import sqrt
N = int(input())
D = int(sqrt(N) + 1)
if N % 2 == 0:
    print(N // 2)
else:
    for i in range(3, D + 1, 2):
        if N % i == 0:
            print(int(1 + (N - i) / 2))
            exit()
    print(1)

Solution (Python):
def gen(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return i
    return n
n = int(input())
d = 0
if n % 2 != 0:
    n -= gen(n)
    d += 1
print(d + n // 2)