概念
在数论中，对于正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的个数(所以会得出一个结论φ(1)=1)，又例如φ(8)=4，因为在1~8的正整数中，唯有1,3,5,7均和8是互为质子数的，数目只有4个。
内容
欧拉函数的通式：
（其中p1，p2，……pn为x的所有质因数，x是不为0的整数）
定义如下：
φ(1)=1，因为在小于等于1的范围里面，和1互质的只有1本身。
通式的例子：
φ(10)=10×(1-1/2)×(1-1/5)=4, ——–10的质因数有2,5
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8，——–30的质因数有2,3,5
φ(49)=49×(1-1/7)=42;——–49的质因数只有7
Attention！每种质因数只有一个
结论1：若n是质数p的k次幂，则，
，因为除了P的倍数外，其他数都是跟n互质的
例如：12=2 * 2 * 3那么
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)
特殊性质：当n为奇质数时，φ(2n)=φ(n), 证明与上述类似。
若n为质数则φ(n)=n-1
补充
☞ 12=2 * 2 * 3，这里的2、2、3都是12的因数，而2和3都是质数，因此把2、3、3叫做12的质因数。假如12=2 * 6，这里的2、6都是12的因素，但是2是质数，而6是合数。因此2可以称作12的质因数，但是6就不能。
同余定理：
如果 a mod b = c 则有(a+kb) mod b =c(k为非0整数)
如果 a mod b = c 则有(ka) mod b =kc (k为正整数)
(a+b) mod c =((a mod c)+(b mod c )) mod c;
(a * b) mod c=((a mod c) * (b mod c)) mod c
代码实现
例1：直接求小于或等于n,且与n互质的个数（只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了）
int Euler(int n)
{
int ans=n;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);//先进行除法防止溢出(ans=ans*(1-1/pi))
while(n%i==0)
{
n/=i;
}
}
}
if(n>1)
{
ans=ans/n*(n-1);
}
return ans;
}筛选模板:求[1,n]之间每个数的质因数的个数
#define size 1000001
int euler[size];
void Init()
{
memset(euler,0,sizeof(euler));
euler[1]=1;
for(int i=2;i < size;i++)
｛
if(!euler[i])
｛
for(int j=i;j < size;j+=i)
{
if(!euler[j])
｛
euler[j]=j;
euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
｝
}
｝
｝
}