思路是hdu6134的简化版，只需要在外面套上一个枚举素数就行了。
http://www.cnblogs.com/autsky-jadek/p/7491730.html
#include<cstdio>
using namespace std;
#define N 10000000
bool notpri[N+5];
int pri[N+5],mu[N+5],sum[N+5];
typedef long long ll;
void shai_mu()
{
notpri[1]=1; mu[1]=1;
for(int i=2;i<=N;i++){
if(!notpri[i]){
pri[++pri[0]]=i;
mu[i]=-1;
}
for(int j=1;j<=pri[0];j++){
if((ll)i*(ll)pri[j]>(ll)N){
break;
}
notpri[i*pri[j]]=1;
mu[i*pri[j]]=-mu[i];
if(i%pri[j]==0){
mu[i*pri[j]]=0;
break;
}
}
}
sum[1]=mu[1];
for(int i=2;i<=N;i++){
sum[i]=sum[i-1]+mu[i];
}
}
int n;
int main(){
shai_mu();
scanf("%d",&n);
ll ans=0;
for(int i=2;i<=n;++i){
if(!notpri[i]){
int nn=n/i;
for(int j=1;j<=n/i;){
ans+=(ll)(sum[nn/(nn/j)]-sum[j-1])*(ll)(nn/j)*(ll)(nn/j);
j=nn/(nn/j)+1;
}
}
}
printf("%lld\n",ans);
return 0;
}