No.3296 81-like number
Problem Statement
A number that can be expressed as $p^n$ using a prime $p$ and an integer $n$ greater than or equal to $2$ is defined as an 81-like number.
For example, $81, 125, 2401$ can be expressed as $3^4, 5^3, 7^4$ respectively, so they are 81-like numbers.
On the other hand, numbers such as $6, 11, 144$ cannot be expressed in the form $p^n$ using a prime $p$ and an integer $n$ greater than or equal to $2$,
so they are not 81-like numbers.
Given an integer $N$, find the sum of all 81-like numbers less than or equal to $N$.
Under the given constraints, it is guaranteed that the answer is less than $2^{63}$.
Constraints
- $2 \leq N \leq 10^{10}$
- $N$ is an integer.
Input
$N$
Output
Print the sum of all 81-like numbers less than or equal to $N$ in $1$ line.
Sample
Sample 1
Input
81
Output
315
The 81-like numbers less than or equal to $81$ are $4, 8, 9, 16, 25, 27, 32, 49, 64, 81$, so print their sum, $315$.
Sample 2
Input
216
Output
858
Sample 3
Input
10000000000
Output
30756925116342
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
くらげ
sepa38