Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function.
The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$.
For simplify, I'd like using $S(n)$ to represent for $\sum_{i=1}^n \phi(i)$.
The algorithm mainly uses the formula: $$\sum_{i=1}^nS(\frac{N}{i})=\frac{N(N+1)}{2}$$ as we know $\frac{N}{i}$ has $O(\sqrt{N})$ different results, so does $S(\frac{N}{i})$, now every thing is prepared and the algorithm works as:
1.Calculate the table of $\phi$ up to $N^\frac{2}{3}$ by sieve of eratosthenes, and the corresponding $S$ is known.
2.Use the formula above, then $S(N)=\frac{N(N+1)}{2}-\sum_{i=2}^nS(\frac{N}{i})$, use the speed-up trick and calculate the remains like $S(\frac{N}{2})$ by recursion.
And here are my questions:
1.How to analyse the time complexity of this algorithm.
2.The calculation in step 1. involves a constant $\frac{2}{3}$, and I wonder if there exist a better constant which could improve the total time complexity, for example $1-\frac{1}{e}$ or $\frac{7}{10}$.
3.Any better algorithm than this in calculating the sum of $\phi$ function?