欧拉函数定义和计算——算法笔记

欧拉函数定义：

  在数论中，对正整数n，欧拉函数 是小于或等于n的正整数中与n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。例如φ(8)=4，因为1,3,5,7均和8互质。(来自维基百科）

欧拉定理：

  对于正整数N，代表小于等于N的与N互质的数的个数，记作φ(N).   例如φ(8)=4，因为与8互质且小于等于8的正整数有4个，它们是：1,3,5,7.

欧拉函数通式：

  φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn)

欧拉函数的直接实现：

根据欧拉函数定理和通式：

//欧拉函数直接筛选 long long direct_phi(long long x) { long long ans = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ans = ans - ans / i; 这个对应的就是欧拉函数的通式 while(x % i == 0){ // 完全筛去 i 因子，确保下一个得到的 i 是 n 的素因子 x = x / i; } } } if (x > 1) { // 为了保证防止未除掉的素因子出现 ans = ans - ans / x; } return ans; }

欧拉函数的线性筛选：

根据以下三条性质：

  φ( p ) = p - 1  φ(p * i) = p * φ( i )   （当p % i == 0时）  φ(p * i) = ( p - 1 ) * φ( i )    (当p % i != 0时) #define N 1000006 int prime[N], mark[N]; // prime 为素数数组， mark 标记是否为素数 int phi[N], indexs = 0; // phi[i] 为φ(i), indexs 为出现素数的个数 //欧拉函数线性筛 void line_phi(int n) { phi[1] = 1; // φ(1) = 1； for (int i = 2; i <= n; i++) { if (! mark[i]) { // 如果是素数(为0) prime[++indexs] = i; //进素数数组，指针加 1 phi[i] = i - 1; } for (int j = 1; j <= indexs; j++) { if (i * prime[j] > n) break; mark[i * prime[j]] = 1; // 标记 i * prime[j] 不是素数 if (i % prime[j] == 0) { //应用性质 1 phi[i * prime[j]] = phi[i] * prime[j]; break; } else { phi[i * prime[j]] = phi[i] * (prime[j] - 1); //应用性质 3 } } } }

还有其他的方法以后慢慢积累。