Function sieve

code/mathematics/summatory_phi.cpp:12–18

    ans += sp[i] * (n/i - max(done, n/(i+1)));
  return mem[n] = n*(n+1)/2 - ans; }
void sieve() {
  for (int i = 1; i < N; i++) sp[i] = i;
  for (int i = 2; i < N; i++) {
    if (sp[i] == i) {
      sp[i] = i-1;
      for (int j = i+i; j < N; j += i) sp[j] -= sp[j] / i; }
    sp[i] += sp[i-1]; } }
// vim: cc=60 ts=2 sts=2 sw=2: