欧拉函数:求少于或等于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//////////////////////////////////
14445149 | hankcs | 2407 | Accepted | 132K | 0MS | C++ | 731B | 2015-07-21 19:53:04 |