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.

分堆互质

算法标签

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}$