1 #include <map>  2 #include <set>  3 #include <stack>  4 #include <queue>  5 #include <cmath>  6 #include <ctime>  7 #include <string>  8 #include <vector>  9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17  18 #define N 400008              19 #define M 50008     20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1  23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo  = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/  31 const int maxn = 100008; 32 vector <int> p[N]; 33  34 int n,m; 35 int fa[N],val[N],mn[N],rev[N],c[N][2],st[N],ln[N],rn[N]; 36 LL ans[maxn]; 37  38 bool isroot(int k){ 39     return c[fa[k]][0]!=k && c[fa[k]][1]!=k; 40 } 41 void pushup(int x){ 42     int l=c[x][0],r=c[x][1]; 43     mn[x]=x; 44     if  (val[mn[l]]<val[mn[x]]) mn[x]=mn[l]; 45     if  (val[mn[r]]<val[mn[x]]) mn[x]=mn[r]; 46 } 47 void pushdown(int x){ 48     int l=c[x][0],r=c[x][1]; 49     if (rev[x]){ 50         if (l) rev[l]^=1; 51         if (r) rev[r]^=1; 52         rev[x]^=1; 53         swap(c[x][0],c[x][1]); 54     } 55 } 56 void rotate(int x){ 57     int y=fa[x],z=fa[y],l,r; 58     if (c[y][0]==x) l=0; else l=1; r=l^1; 59     if (!isroot(y)){ 60         if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; 61     } 62     fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 63     c[y][l]=c[x][r]; c[x][r]=y; 64     pushup(y); pushup(x); 65 } 66 void splay(int x){ 67     int top=0; st[++top]=x; 68     for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; 69     while (top) pushdown(st[top--]); 70     while (!isroot(x)){ 71         int y=fa[x],z=fa[y]; 72         if (!isroot(y)){ 73             if (c[y][0]==x^c[z][0]==y) rotate(x); 74             else rotate(y); 75         } 76         rotate(x); 77     } 78 } 79 void access(int x){ 80     int t=0; 81     while (x){ 82         splay(x); 83         c[x][1]=t; 84         pushup(x); 85         t=x; x=fa[x]; 86     } 87 } 88 void rever(int x){ 89     access(x); splay(x); rev[x]^=1; 90 } 91 void link(int u,int v){ 92     rever(u); fa[u]=v; 93 } 94 void cut(int u,int v){ 95     rever(u); access(v); splay(v); fa[c[v][0]]=0; c[v][0]=0; pushup(v); 96 } 97 int find(int u){ 98     access(u); splay(u); 99     while (c[u][0]) u=c[u][0];100     return u;101 }102 int query(int u,int v){103     rever(u); access(v); splay(v); return mn[v];104 }105 int main(){106     for (int i=1;i<=maxn;i++)107         for (int j=i;j<=maxn;j+=i)108             p[j].push_back(i);109     int now=0;110     val[0]=INF;111     rep(i,1,maxn){112         val[++now]=INF;113         mn[now]=now;114     }115     ans[1]=0;116     LL tmp=0;117     for (int u=1;u<=maxn;u++){118        for (int i=p[u].size()-2;i>=0;i--)119         {120             int v=p[u][i];121             int flag=1;122             if (find(u)==find(v)){123                 int t=query(u,v);124                 if (v>val[t]){125                     cut(ln[t],t);126                     cut(rn[t],t);127                     tmp-=val[t];128                     flag=1;129                 }130                 else flag=0;131             }132             if (flag){133                 mn[++now]=now; val[now]=v; ln[now]=u; rn[now]=v;134                 link(now,u); link(now,v);135                 tmp+=v;136             }137         }138         ans[u]=tmp;139     }140     while (~scanf("%d",&n)){141         printf("%lld\n",ans[n]);142     }143 }