本文共 742 字，大约阅读时间需要 2 分钟。

欧拉函数的定义:

在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。 φ函数的值： φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))……(1-1/p(n)) 其中p(1),p(2)…p(n)为x的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。

例如:

φ(10)=10×(1-1/2)×(1-1/5)=4; φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8; φ(49)=49×(1-1/7)=42;

欧拉函数模板

(1)直接求小于或等于n,且与n互质的个数:

int Euler(int n){    int ret=n;    for(int i=2; i<=sqrt(n); i++)        if(n%i==0)        {            ret=ret/i*(i-1);                   //先进行除法防止溢出(ret=ret*(1-1/p(i)))            while(n%i==0)                n/=i;        }    if(n>1)        ret=ret/n*(n-1);    return ret;}

（2）筛选模板:求[1,n]之间每个数的质因数的个数

#define size 1000001int euler[size];void Init(){     memset(euler,0,sizeof(euler));          euler[1]=1;     for(int i=2;i

 

转载地址：http://hpyzi.baihongyu.com/