这个算法是在线性时间内在筛素数的同时求出所有数的欧拉函数(对于正整数n,小于等于n的数中与n互质的数的数目。

先明确几个性质（p为质数）：

　　1*　　φ（p）=p-1。（显然，【1，p-1】内的任意整数都与p互质）。

　　2*　　若t mod p

欧拉函数