ZOJ Problem Set - 3808
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.
There are about 200 cases. Each case is a positive integer number n in a line. (n≤ 109)
For each case, output the sum of Φ*(1), Φ*(2), ... Φ*(n).
6 99 100
13 3475 3547
Author: ZHOU, Yuchen
Source: ZOJ Monthly, August 2014