subtractDivisor

Cho trước một số nguyên dương n. Thuật toán sau được áp dụng với nó:

1. Nếu n = 0 thì kết thúc thuật toán
2. Tìm ước số nguyên tố d nhỏ nhất của n
3. Thay giá trị của n bằng n - d và quay lại bước 1

Hãy xác định xem số lần số lần thực hiện thao tác thứ 3 của thuật toán này là bao nhiêu

Ví dụ:

• Với n = 5 thì subtractDivisor(n) = 1. Vì 5 là số nguyên tố nên 5 cũng là ước số nguyên tố nhỏ nhất của chính nó. Sau khi thực hiện một thao tác trừ thì ta được 0
• Với n = 4 thì subtractDivisor(n) = 2. Trong hai lượt trừ thì ta trừ n cho 2

Đầu vào/Đầu ra:

• [Giới hạn thời gian chạy] 0.5 giây với C++, 3 giây với Java và C#, 4 giây với Python, Go và JavaScript
• [Đầu vào] Long n
  2 ≤ n ≤ 10^10
• [Đầu ra] Long
  Trả về số thao tác trừ mà thuật toán sẽ thực hiện đối với số nguyên n