euler.cpp

来自「数值计算的例子和参考书籍」· C++ 代码 · 共 28 行

#include <stdio.h>
#include <math.h>

int main(void)
{
	int m;
	while(scanf("%d", &m), m != 0)
	{
		int tm = m;
		int euler = m;
		const int t = (int) sqrt(tm); //求euler(m)函数值；
		for(int i = 2; i <= t && i <= tm; i++)
		{
			if(tm % i == 0)
			{
				euler = euler / i * (i - 1);
				while(tm % i == 0) tm /= i;//tm为m的最大质因子；
			}
		}
		if(tm > 1)
		{
			euler = euler / tm * (tm - 1);
		}
		printf("%d\n", euler);
	}
	return 0;
}