305691: CF1076B. Divisor Subtraction

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

输入输出样例

输入样例 #1

5

输出样例 #1

1

输入样例 #2

4

输出样例 #2

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.

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: