【数论】Send a Table, UVa10820 【线性筛法】【欧拉函数】

#include<bits/stdc++.h>
using namespace std;
int n;typedef long long LL;
int phi[50005];
void getphi(int m){
	phi[1]=1;
	for(int i=2;i<=m;i++)if(!phi[i]){
		for(int j=i;j<=m;j+=i){
			if(!phi[j])phi[j]=j;
			phi[j]=phi[j]/i*(i-1);
		}
	}
	for(int i=3;i<=m;i++)phi[i]+=phi[i-1];
	phi[1]=0;
}
int main(){
	ios::sync_with_stdio(false);
	getphi(50000);
	while(cin>>n){
		if(!n)break;
		cout<<phi[n]*2+1<<endl;	
	}
	return 0;
}