Computation of the Totient Summatory Function

An algorithm is devised for computing $\mathrm{\Phi }(n)=\phi (1)+\phi (2)+\cdots +\phi (n)$ in time $\tilde{\mathrm{\Theta }}(n^{2\mathrm{/}3})$ and space $\tilde{\mathrm{\Theta }}(n^{1\mathrm{/}3})$. The starting point is an existing algorithm based on the Dirichlet hyperbola method and the Mertens function. The algorithm is then used to compute $\mathrm{\Phi }({10}^{19})=30396355092701331435065976498046398788$.