首页 > 代码库 > POJ 2407 Relatives 欧拉函数题解
POJ 2407 Relatives 欧拉函数题解
最基本的欧拉函数:
欧拉函数:求小于n的与n互质的个数
欧兰函数公式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数
就是要求这样的式子啦,不过求这条式子,相信有很多种方法可以求,这个不是难题;
不过问题是如何巧妙地求,如何简洁地写出代码。
直接硬求,或者求出质因数之后求都不是巧妙的方法了,参考了下别人的代码才知道可以写的这么巧妙的。
下面程序可以说是连消带打地求式子结果,分解质因子,可以如此简明地把解题思想转化为计算机程序思维,然后转化为代码,这就是高手的境界:
#include <stdio.h> unsigned eulerFunc(unsigned n) { unsigned ans = 1; for (unsigned i = 2; i*i <= n; i++) { if (n % i == 0) { n /= i, ans *= (i-1); while (n % i == 0) n /= i, ans *= i;//把质数除去,巧妙变相分解质因子 } } if (n > 1) ans *= (n-1); return ans; } int main() { int n; while (scanf("%d", &n) && n !=0) { printf("%d\n", eulerFunc(n)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。