法雷级数：法雷级数Fn定义为所有分母小于等于n，并且值介于0到1之间的既约分数（分子分母互素）从小到大排列所组成的序列。即

Fn = { a / b, gcd(a,b) = 1 && 0<=a<=b<=n}~~每次加的都是n中与n互质的数的个数~正式欧拉函数φ（n）

实例如下：

F1 = { 0 / 1, 1 / 1 }
F2 = { 0 / 1, 1 / 2, 1 / 1 }
F3 = { 0 / 1, 1 / 3, 1 / 2, 2 / 3, 1 / 1 }
百科中的法雷级数：
R.亨斯贝尔格著李忠翻译的《数学中的智巧》一书，介绍了法雷级数。这里每一行从0/1开始，以1/1结尾，其它数自左至右将所有的真分数按增加顺序排列；第n行是由所有分母小于或等于n的真分数（分子与分母互质）组成，我们称为n阶法雷级数。如下表：

F1： 0/1 1/1

F2： 0/1 1/2 1/1

F3： 0/1 1/3 1/2 2/3 1/1

F4： 0/1 1/4 1/3 1/2 2/3 3/4 1/1

F5： 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1 //从小到大排的

F6：0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1 //每次加的都 是n中与n互质的数的个数~正式欧拉函数φ（n）

……………………………………

这里我们想问的是第n行Fn的真分数的个数有多少个呢？

我们设Fn的个数为ψ(n), ψ(n)比 ψ(n-1)增加的个数是分母是n，分子比n小且与n互质的数的个数，这正是欧拉函数φ（n）。即

ψ(n)=ψ(n-1)+ φ（n）

ψ（1）=1+φ（1）

ψ（2）=ψ（1）+φ（2）

ψ（3）=ψ（2）+φ（3）

……………………

ψ(n)= ψ(n-1)+ φ（n）

所以 ψ(n)=1+φ（1）+φ（2）+φ（3）+……+φ（n）

很容易证明，当n≥3时，欧拉函数φ（n）是个偶数。由此我们得到除ψ（1）=2是偶数外，法雷级数其它各级的个数都是奇数，并且许多是素数。ψ（1）=2，ψ（2）=3，ψ（3）=5，ψ（4）=7，ψ（5）=11，ψ（6）=13，ψ（7）=19

欧拉函数：

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目~φ函数

φ函数的值
　　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数（讨论的是正整数）。φ(1)=1（唯一和1互质的数就是1本身）。
　　若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
　　欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
　　特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。

φ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
φ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
φ（４９）＝４９×（１－１/７）＝４２。


下面给出求一个很大的数的欧拉函数的思想：假设n=100 0000

先找出100 0000 以内的所有质数，再存在一个数组中，一趟过去（判断n是不是质数：看能不能整除从2到（int）sqrt（n）），依次找出一个出来，它的倍数就不用找了~标记，这样就省了很多的时间~~

再就是找质因数，如n，只要求sqrt（n）的质数的紧跟后面的那个质数的当中的所有的质数，这些质数只要能被n整除的就是n的质因子，都不能被他们整除的说明n是质数~~它的质因子就是自己再根据：

φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为n的所有质因数 ~~得出与n互质的数的个数