分堆互质

算法标签

Level1 数学1 GESP1级

题目背景

为 acjudge 比赛而努力奋斗，打好每一场比赛。

题目描述

正整数 $a$ 与 $b$ 的最大公约数是能同时整除 $a$ 与 $b$ 的最大正整数 $d$。若最大公约数为 $1$，则称 $a$ 与 $b$ 互质。

给定正整数 $n$，将 $1$ 到 $n$ 共 $n$ 个正整数划分为若干堆，需要使每一堆内任意两个数都互质。求最少需要划分成多少堆。

输入格式

一个正整数 $n$。

输出格式

输出一个整数，表示最少需要的堆数。

样例

2

1

5

2

样例解释

样例1：将 $\{1,2\}$ 放在一堆，它们互质，因此堆数为 $1$。
样例2：一种方案是 $\{1,2,5\}$ 和 $\{3,4\}$，各堆内元素两两互质，堆数为 $2$。

数据范围

$1 \le n \le 10^{18}$