给定整数n，那么n的唯一的分解式如下
欧拉函数的定义：
phi(n) 为1->n中与n互素的数的个数。与n互素，就与所有n的所有素数因子pi互素， 与pi互素和不是pi的倍数是等价的
那么可以用容斥定理来求解phi(n)，从n个数中减去是1个素因子倍数的个数，然后加上同时是2个素因子倍数的个数，然后减去同时是3个素数因子的倍数的个数
n/pi 为有多少个数是pi的倍数
那么就得到一个公式
|s|代表的是集合中元素的个数
对于
的任意子集s，不与其中任何一个元素互素的个数是
比如:
我们将上述的公式变形一下得到
我们等价呢，因为这个式子的展开式的每一项是1或者
，那么展开之后，和原来推导过程的式子是一样的
那么可以得到代码
1 int euler(int n) 2 { 3 int m = sqrt(n) + 0.5; 4 int ans = n; 5 for (int i = 2; i <= m; ++i) 6 if (n%i == 0) 7 { 8 ans = ans / i * (i - 1); 9 while (n%i == 0) n /= i; 10 } 11 if (n > 1) ans = ans / n *(n - 1); 12 return ans; 13 }
如果要求出1->n所有数字的欧拉函数值，那么可以用类似筛法的方法得到
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 19 */ 20 const int N = 1000000 + 10; 21 int phi[N]; 22 void phiTable(int n, int *phi) 23 { 24 int i, j; 25 for (i = 2; i <= n; ++i) phi[i] = 0; 26 phi[0] = 0; 27 phi[1] = 1; 28 for (i = 2; i <= n; ++i) 29 { 30 if (!phi[i])//素数肯定没有被筛过 31 for (j = i; j <= n; j += i) 32 { 33 if (!phi[j]) phi[j] = j; 34 phi[j] = phi[j] / i * (i - 1);//因为i是素数，即i是j的素数因子 35 } 36 } 37 } 38 39 40 int main() 41 { 42 43 phiTable(100, phi); 44 int i; 45 for (i = 2; i <= 100; ++i) 46 printf("%d ", phi[i]); 47 return 0; 48 }
原文：http://www.cnblogs.com/justPassBy/p/4489040.html
