题解

题目描述

小红需要构造一个长度为 $n$ 的数组，数组中的每个元素 $a_i$ 满足 $1 \leq a_i \leq n$。要求任意两个下标 $i$ 和 $j$（$i \neq j$ 且 $\gcd(i, j) \neq 1$）对应的元素 $a_i$ 和 $a_j$ 必须不同。求数组中最少需要多少种不同的数字。

题目内容

小红想构造一个长度为 $n$ 的数组 {$a_1,a_2,....,a_n$}，其中 $a_i$ 满足 $1≤ a_i ≤ n$ ，$[1,n]$ 的每个数字可以重复使用也可以不用。

她希望任意两个索引 $i,j$ 满足 $(i≠j$ 且 $gcd(i,j)≠1)$ 时，其两个位置的权值不相等，即 $a_i ≠ a_j$ ，请你帮助小红判断最少需要多少种不同的数字。

输入描述

一个整数 $n(1 ≤ n ≤ 10^9)$ ，表示小红希望你构造的数组长度。

输出描述

一个整数，表示数组中不同数字的个数的最小值。

样例1

输入

3

输出

1

说明

数组下标依次为 $[1,2,3]$ ，对于任意的两个索引 $i,j(i ≠ j)$ 都满足 $gcd(i,j) = 1$ ，所以我们可以只使用 $2$ 来填数组 ，为 $[2,2,2]$，当然 $[1,1,1]$ 或者 $[3,3,3]$ 也是正确的。

样例2

输入

4

输出

2