uva 11426 欧拉函数的运用

//uva 11426 欧拉函数的运用 
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 4000051;
bool is_prime[maxn];
int prime[maxn],phi[maxn];
ll a[maxn];
void getphi(){
	memset(is_prime,0,sizeof(is_prime));
	phi[1] = 1;
	for(int i=2;i<maxn;i++){
		if(!is_prime[i]){
			prime[++prime[0]] = i;
			phi[i] = i-1;
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
			is_prime[prime[j]*i] = 1;
			if(i%prime[j]==0){
				phi[i*prime[j]] = phi[i]*prime[j];
			}else{
				phi[i*prime[j]] = phi[i]*(prime[j]-1);
			}
		}
	}
}
void solve(){
	getphi();
	for(int i=2;i<maxn;i++){
		for(int j=1;j*i<maxn;j++){
			a[j*i]+=j*phi[i];
		}
	}
	for(int i=1;i<maxn;i++)
		a[i]+=a[i-1];
}
int main() {
	solve();
	int n;
	while(scanf("%d",&n)&&n){
		printf("%lld\n",a[n]);
	}
	return 0;
}