2 shunfurh shunfurh 于 2017.08.29 09:17 提问

The Sum of Unitary Totient

Let d is the divisor of n, then d is called unitary divisor of n if the greatest common divisor of d and n/d is 1.

Let Φ* is the unitary totient function defined as Φ*(n)=(p1a1-1)(p2a2-1)...(prar-1) for n=p1a1p2a2...prar where p1, p2, ..., pr are different prime numbers.

You can also find unitary totient function on this oeis page for more information.

Your task is to calculate the sum of Φ*(1), Φ*(2), ... Φ*(n), which n can be up to 109.

Input

There are about 200 cases. Each case is a positive integer number n in a line. (n≤ 109)

Output

For each case, output the sum of Φ*(1), Φ*(2), ... Φ*(n).

Sample Input

6
99
100
Sample Output

13
3475
3547

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.13 00:40
已采纳
Csdn user default icon
上传中...
上传图片
插入图片