POJ 2407 Relatives 题解《挑战程序设计竞赛》

POJ 2407 Relatives 

欧拉函数：求少于或等于n的数中与n互素的数的个数；n <= 1,000,000,000。

4.1更加复杂的数学问题 

计数 

就是裸的欧拉……函数嘛。

唠唠嗑，最近发生好多事情。感觉公司里大家往往很关心算法的效果，但并不怎么关心算法的速度，反正上Hadoop集群，并行化似乎是万金油的样子。

#include <iostream>
using namespace std;

//return phi(n) , 复杂度O(sqrt(n))
inline int phi(int x)
{
	int ret = x;
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			ret = ret / i * (i - 1);
			for (; x % i == 0; x /= i);
		}
	}
	if (x != 1)
	{
		ret = ret / x * (x - 1);
	}
	return ret;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (~scanf("%d", &n) && n)
	{
		printf("%d\n", phi(n));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2407 Relatives 题解《挑战程序设计竞赛》