解题思路

本题的本质是一个图着色问题。将每一枚符文看作一个节点，如果两个符文的编号 $i$ 和 $j$（$i \neq j$）满足 $\gcd(i, j) > 1$，则在这两个节点之间连一条边。要求为所有节点分配属性（颜色），使得有边相连的两个节点颜色不同，求最少需要的颜色数。

关键观察：

• 所有偶数编号的符文（2, 4, 6, …）两两之间的最大公约数至少为 2，因此这些符文必须两两分配不同的属性。偶数编号的符文总数为 $\lfloor n/2 \rfloor$ 个，所以最少属性种类数至少为 $\lfloor n/2 \rfloor$。
• 对于奇数编号的符文，可以通过合理的属性分配，与偶数编号符文共用某些属性而不引发冲突，因为奇数编号之间或奇偶组合之间可能互质（最大公约数为 1），从而保证属性种类数不必超过 $\lfloor n/2 \rfloor$。