You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

正整数 $a$ 和 $b$ 的最大公因数是满足 $a,b$ 同时是 $d$ 的倍数的最大的正整数 $d$。

而正整数 $a$ 和 $b$ 互质，指的是 $a$ 和 $b$ 的最大公因数为 $1$。

给定一个正整数 $n$，求最少把 $1\sim n$ 共 $n$ 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数表示最少的堆数。

输入输出样例

2

1

样例 $\tt \#1$说明

• 一种合法方案是把$1,2$放在同一堆，则$1,2$的最大公因数是$1$，它们互质，所以满足要求。

5

2

样例 $\tt \#2$说明

• 一种合法方案是把$1,2,5$放在同一堆，$3,4$放在同一堆，可以验证是满足要求的。

数据范围

• 对于 $50\%$的数据，$1\leq n\leq10$。
• 对于 $70\%$的数据，$1\leq n \leq10^3$。
• 对于 $100\%$的数据，$1\leq n\leq10^{18}$。