阅读程序（第三题）：线性筛求素数表与欧拉函数

阅读下面程序，完成后面的判断题和单选题。判断题正确填 A，错误填 B。程序读入一个整数 n（1 ≤ n ≤ 1000000）。第一行输出 1 到 n 之间的素数个数，第二行输出 Σ_{i=1}^{n} φ(i)。

#include <cstdio>

const int MAXN = 1000005;
int phi[MAXN], primes[MAXN], cnt = 0;
bool vis[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * primes[j] <= n; ++j) {
            int p = primes[j];
            vis[i * p] = true;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    long long s = 0;
    for (int i = 1; i <= n; ++i) s += phi[i];
    printf("%d\n%lld\n", cnt, s);
    return 0;
}