```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=40000+5;
int phi[N];
void euler(int n)
{
phi[1]=1;
for (int i=2;i<=n;i++)
phi[i]=i;
for (int i=2;i<=n;i++)
{
if (phi[i]==i)
for (int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);
}
}
int main()
{
int n;
scanf("%d",&n);
euler(n);
ll ans=3;
for (int i=2;i<=n;i++)
ans+=2*phi[i];
printf("%lld\n",ans);
return 0;
}
```
by Carbon @ 2018-09-27 00:15:02
~~ans的初值，不应该是2吗~~
by Carsonn @ 2018-10-27 11:22:05