仪仗队

　

仪仗队

#include <iOStream>
#include <cstdio>
using namespace std;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')  f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}
const int N=50000;
int n,phi[N],p[N],num,ans;
bool f[N];
int main()
{
	n=read();
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!f[i])  p[++num]=i,phi[i]=i-1;
		for(int j=1;j<=num&&i*p[j]<=n;j++)
		{
			f[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			else phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
	for(int i=2;i<n;i++)  ans+=phi[i];
	if(n==1)  cout<<0;
	else  cout<<ans*2+3;
	return 0;
}

相关阅读