本题可以转化为图染色问题：将 nnn 个位置看作 nnn 个顶点，若两个位置的编号 iii 与 jjj 满足 gcd(i,j)>1\gcd(i, j) > 1gcd(i,j)>1，则在顶点 iii 与 jjj 之间连一条边。题目要求相邻顶点必须染不同颜色，最少需要的颜色数就是该图的色数。
观察图的结构：所有偶数编号的位置两两之间 gcd≥2\gcd \ge 2gcd≥2，因此构成一个完全图（团）。偶数位置共有 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ 个，该团需要至少 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ 种不同颜色，所以答案至少为 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋。
可以构造一种染色方案恰好使用 ⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ 种颜色：
在一场游戏中，有 nnn 个位置按顺序编号为 1,2,…,n1, 2, \dots, n1,2,…,n。你需要为每个位置分配一个整数作为它的标签。
规则如下：对于任意两个不同的位置 iii 和 jjj，如果它们的编号不互质（即 gcd(i,j)>1\gcd(i, j) > 1gcd(i,j)>1），则这两个位置的标签必须不同；如果编号互质，则对标签是否相同没有限制。
请你计算，在满足上述条件的前提下，最少需要准备多少种不同的标签。
约束：位置总数 nnn 满足 1≤n≤1091 \le n \le 10^91≤n≤109。
本题属于以下题库，请选择所需题库进行购买
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.
Using your CodeFun2000 universal account
