%b5%dd%cd%c6euler.cpp

来自「ACM经典算法ACM经典算法ACM经典算法」· C++ 代码 · 共 16 行

for(i=1;i<=mxn;i++)
	phi[i]=i;
for(i=2;i<=mxn;i+=2) phi[i]/=2;
for(i=3;i<=mxn;i+=2)
{
	if(phi[i]==i)
	{
		j=i;
		while(j<=mxn)
		{
			phi[j]=phi[j]/i*(i-1);
			j+=i;
		}
	}
}