P16637 春季限定独立集问题
题目背景
题目描述
有一棵 $n$ 个点的有根树，根是 $1$。
对于 $i>1$，记 $m_i$ 为 $i$ 的最小质因子，那么 $i$ 的父亲结点就是 $\frac{i}{m_i}$。
求这棵树的最大独立集的大小。
输入格式
一行一个非负整数 $n$ 代表树的点数。
输出格式
一行一个非负整数代表这棵树的最大独立集大小。
说明/提示
- 对于 $10\%$ 的数据，$1\leq n\leq 10^7$。
- 对于 $30\%$ 的数据，$1\leq n\leq 10^8$。
- 对于 $50\%$ 的数据，$1\leq n\leq 10^{9}$。
- 对于 $70\%$ 的数据，$1\leq n\leq 10^{10}$。
- 对于 $100\%$ 的数据，$1\leq n\leq 10^{11}$。