帮我写一段C++基于线性筛的自然数幂求和算法，规模为1e6

当然可以，下面是基于线性筛的自然数幂求和算法，规模为1e6：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAXN 1000000

int prime[MAXN + 1];
int phi[MAXN + 1];
long long ans[MAXN + 1];

void get_prime() {
    memset(prime, 0, sizeof(prime));
    memset(phi, 0, sizeof(phi));
    memset(ans, 0, sizeof(ans));
    phi[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (prime[i] == 0) {
            prime[++prime[0]] = i;
            phi[i] = i - 1;
            ans[i] = i - 1;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= MAXN; j++) {
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                ans[i * prime[j]] = ans[i] + phi[i * prime[j]];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
                ans[i * prime[j]] = ans[i] + ans[prime[j]];
            }
        }
    }
}

int main() {
    get_prime();
    long long sum = 0;
    for (int i = 1; i <= MAXN; i++) {
        sum += ans[i];
    }
    printf("%lld\n", sum);
    return 0;
}

希望这份代码能够帮助到你。