4295: 互质划分（coprime）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
# 互质划分（coprime）
### 题目描述
正整数 $a$ 和 $b$ 的最大公因数是满足 $a,b$ 同时是 $d$ 的倍数的最大的正整数 $d$。
而正整数 $a$ 和 $b$ 互质，指的是 $a$ 和 $b$ 的最大公因数为 $1$。
给定一个正整数 $n$，求最少把 $1\sim n$ 共 $n$ 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。
输入
### 输入格式
一行一个正整数 $n$。
输出
### 输出格式
一行一个整数表示最少的堆数。
样例输入 复制
2样例输出 复制
1提示
### 样例 1 输入
```
2
```
### 样例 1 输出
```
1
```
### 样例 1 解释
一种合法方案是把 $1,2$ 放在同一堆，则 $1,2$ 的最大公因数是 $1$，它们互质，所以满足要求。
### 样例 2 输入
```
5
```
### 样例 2 输出
```
2
```
### 样例 2 解释
一种合法方案是把 $1,2,5$ 放在同一堆，$3,4$ 放在同一堆，可以验证是满足要求的。
### 数据规模与约定
对于 $50\%$ 的数据，$1\leq n\leq 10$。
对于 $70\%$ 的数据，$1\leq n\leq 10^3$。
对于 $100\%$ 的数据，$1\leq n\leq 10^{18}$。