#P17785. 春季限定独立集问题
春季限定独立集问题
题目描述
有一棵 个点的有根树,根是 。
对于 ,记 为 的最小质因子,那么 的父亲结点就是 。
求这棵树的最大独立集的大小。
输入格式
一行一个非负整数 代表树的点数。
输出格式
一行一个非负整数代表这棵树的最大独立集大小。
输入输出样例 #1
输入 #1
7
输出 #1
4
输入输出样例 #2
输入 #2
114514
输出 #2
68372
输入输出样例 #3
输入 #3
10000000000
输出 #3
5971085299
说明/提示
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。