No.1322 Totient Bound
chocorusk
noimiProblem Statement
For a positive integer $n$, let $\varphi (n)$ denote the number of integers between $1$ and $n$, inclusive, that are coprime to $n$.
Find the number of positive integers $x$ satisfying $\varphi (x)\leq N$. It can be shown that the answer is finite under the constraints of this problem.
Input
$N$
- $1\leq N\leq 10^{10}$
- $N$ is an integer.
Output
Output the answer.
Sample
Sample 1
Input
4
Output
9
The values of $\varphi (x)$ for $x=1,2, \ldots , 12$ are, in order, $1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4$. It can be shown that $\varphi(x)>4$ when $x>12$, so the positive integers $x$ satisfying $\varphi(x)\leq 4$ are $1, 2, 3, 4, 5, 6, 8, 10, 12$, for a total of $9$.
Sample 2
Input
9
Output
18
Sample 3
Input
334
Output
643
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。