
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)=(p_{1}^{a1}1)(p_{2}^{a2}1)...(p_{r}^{ar}1) for n=p_{1}^{a1}p_{2}^{a2}...p_{r}^{ar} where p_{1}, p_{2}, ..., p_{r} 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 10^{9}. InputThere are about 200 cases. Each case is a positive integer number n in a line. (n≤ 10^{9}) OutputFor each case, output the sum of Φ^{*}(1), Φ^{*}(2), ... Φ^{*}(n). Sample Input6 99 100 Sample Output13 3475 3547 Author: ZHOU, Yuchen Source: ZOJ Monthly, August 2014 