埃式筛

$O(nlogn)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 1000010;

LL sum;
int phi[N];
bool st[N];

int n;

void euler(int n){
    for(int i = 1; i <= n; i++) phi[i] = i;
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            for(int j = i; j <= n; j += i){
                st[j] = true;
                phi[j] = phi[j] / i * (i - 1);
                }
            }
        }
}

int main(){
    scanf("%d", &n);
    euler(n);
    for(int i = 1; i <= n; i++) sum += phi[i];
    printf("%lld\n", sum);
    return 0;
}