题目内容

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

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

题目大意
给定正整数 n，要构造长度为 n 的数组 a[1..n]，每个元素取自 1..n，可重复使用。要求对于任意 i≠j 且 gcd(i,j)>1 的一对下标，必须满足 a[i]≠a[j]。问最少需要多少种不同的数字。

思路

1. 把下标 1…n 看成图的顶点，若 gcd(i,j)>1 则顶点 i、j 之间连边。