题目内容

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