%bd%cf%c2%fd%b5%c4euler.cpp

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

unsigned euler(unsigned x)
{
	unsigned i,res=x;
	for(i=2;i<(int)sqrt(x*1.0)+1;i++)
	{
		if(x%i==0)
		{
			res=res/i*(i-1);
			while(x%i==0)
				x/=i;
		}
	}
	if(x>1) res=res/x*(x-1);
	return res;
}