本文主要向大家介绍了C/C++知识点之欧拉函数+素数筛，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

 欧拉函数，就是欧拉发现的一个关于求素数的的公式，然后我们编个函数实现这个公式。
欧拉发现求小于等于n的正整数中有多少个数与n互质可以用这个公式：
euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。euler(1)=1（唯一和1互质的数就是1本身）。 
欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。
其实直接看模板加注解想想就能看懂
筛选的原理就是找出n的因子，剔除含有n的因子的数，即剔除与n不互质的数
既然是求与n互质的个数，那我们可以直接筛选，看模板：
int phi(int n)
{    int res=n;                  /假设现有n个数与n互质，开始筛选剔除
 for(i=2;i*i<=n;i++)
{    if(n%i==0)                /若这个数是n的因子，减去n以下含有这个因子的数个数，假设n=8，小于等于8，2为公因子的有8/2=4个
   {   res-=res/i;
       while(n%i==0)            /将n不断整除这个因子  
       n=n/i;
    }
}
if(n>1)             /若n大于1，则此时的n也是一个除1以外的因子
res-=res/n;            
return res;
}
有时候还用到多个数的欧拉值，因此需要对1到n的数都求出欧拉值，就是打表。
将1到n的欧拉值求出并存储到数组，筛选法，代码：
void phi(int n)                         上边的看懂了，下边这个求多个数的也类似
{   for(int i=1;i<=n;i++)
     p[i]=i;                   赋原值
  for(int i=2;i<=n;i++)
      if(p[i]==i)                
      {   for(int j=i;j<=n;j+=i)          筛选
           p[j]=p[j]-p[j]/i;
      }
}
 
素数筛：就是让你判断任意一个数是否为素数，若问一个求一个显然会超时，所以首先需要把素数都求出来，用筛选法求的，所以叫素数筛。
原理就是若一个数有除1和它本身以外的因子就将它标记不是素数，最后无标记的就是素数。
直接看代码加注解：
#include 
#include 
#define MAX 1000001
int flag[MAX];
int main()
{    memset(flag,0,sizeof(flag));
     flag[1]=1;               /1代表不是素数，0代表是素数
    for(int i=4;i<MAX;i+=2)
      flag[i]=1;              /先将偶数先标记不是
    for(int i=3;i*i<MAX;i+=2)  
    for(int j=i*i;j<MAX;j+=i)   /奇数的倍数标记不是
      flag[j]=1;
int n;                           
while(cin>>n)
{   if(flag[n]==0)
    cout<<"YES"<<endl;
    else
   cout<<"NO"<<endl;
}
}
 素数筛常用于让你判断大量素数，或求大量素数，当然如果数目很少，就按常规判断就好了
 

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！