std算法

欧拉筛预处理phi前缀和。

时间复杂度

O(n + c)

C++ 代码

const int Maxn = 1005; int timer = 0;
int T, n, cnt = 0, prime[Maxn], vis[Maxn], phi[Maxn];
inline void Sieve(void) { phi[1] = 1;
    for (int i = 2; i < Maxn; i++) {
        if (!vis[i]) prime[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && prime[j] * i < Maxn; j++) {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0) { phi[prime[j] * i] = phi[i] * prime[j]; break; }
            phi[prime[j] * i] = phi[i] * (prime[j] - 1);
        }
    } for (int i = 1; i < Maxn; i++) phi[i] += phi[i - 1];
}

signed main(void) {
//  file("");
    Sieve();
    for (read(T); T; T--) { read(n);
        writeln(++timer, ' ');
        writeln(n, ' '), writeln(2 * phi[n] + 1);
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}