打表找规律：
当n为质数是，GCD(n)=n;
当n为质数k的q次方时，GCD(n)=k;
其他情况，GCD(n)=1.
代码如下：
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#define ll long long
#define M 1000001
using namespace std;
ll a[M];
int prime[],cnt;
bool f[M];
int fac(int n)
{
for(int i=;i<cnt&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==){
n/=prime[i];
while(n%prime[i]==) n/=prime[i];
if(n==) return prime[i];
return ;
}
}
return ;
}
void init()
{
int i,j,k;
cnt=;
for(i=;i<M;i++){
if(f[i]==) prime[cnt++]=i;
for(j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
int main()
{
int i,k,n;
init();
while(scanf("%d",&n)!=EOF){
ll ans=;
for(i=;i<=n;i++){
if(f[i]==) ans+=i;
else{
k=fac(i);
if(k) ans+=k;
else ans+=;
}
}
printf("%I64d\n",ans);
}
return ;
}