P16637 Spring Limited Independent Set Problem


There is a rooted tree with $n$ nodes, and the root is $1$. For $i > 1$, let $m_i$ be the smallest prime factor of $i$. Then the parent of node $i$ is $\frac{i}{m_i}$. Find the size of the maximum independent set of this tree.

One line with a non-negative integer $n$, representing the number of nodes in the tree.

One line with a non-negative integer, representing the size of the maximum independent set of this tree.

# Constraints - For $10\%$ of the testdata, $1 \leq n \leq 10^7$. - For $30\%$ of the testdata, $1 \leq n \leq 10^8$. - For $50\%$ of the testdata, $1 \leq n \leq 10^{9}$. - For $70\%$ of the testdata, $1 \leq n \leq 10^{10}$. - For $100\%$ of the testdata, $1 \leq n \leq 10^{11}$. Translated by ChatGPT 5