此题不用杜教筛，只用欧拉函数也能过……（时间复杂度 $O(nlogn)$ ）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,A[10000010],B[10000010],f[10000010],ans;
bool noPM[10000010];
vector<int> prime;
void init(){
	for(int i=2;i*i<=n;i++){
		if(!noPM[i]){
			for(int j=i*i;j<=n;j+=i) noPM[j]=1;
		}
	}
	for(int i=2;i<=n;i++){
		if(!noPM[i]) prime.push_back(i);
	}
	return;
}
signed main(){
	scanf("%lld",&n);
	init();
	for(int i=1;i<=n;i++) A[i]=B[i]=1;
	for(int i=0;i<prime.size();i++){
		int p=prime[i];
		for(int j=p;j<=n;j+=p){
			A[j]*=p-1;
			B[j]*=p;
		}
	}
	for(int i=1;i<=n;i++) f[i]=i/B[i]*A[i];
	for(int i=1;i<=n;i++) f[i]+=f[i-1];
	for(int i=0;i<prime.size();i++) ans+=(f[n/prime[i]]-1)*2+1;
	printf("%lld",ans);
	return 0;
}

昨天写的，今天发帖