欧拉函数的求法

本文主要是介绍欧拉函数的求法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 欧拉函数（模板）
标签： includeini
2010-07-30 09:07 1333人阅读 评论(1) 收藏 举报分类： 模板集（陆续更新）（13）  
版权声明：本文为博主原创文章，未经博主允许不得转载。[c-sharp] view plain copy
#include <iostream>  
using namespace std;  
#define N 100000001  int euler(int n)  
{  int ans=1;  int i;  for(i=2;i*i<=n;i++)  {  if(n%i==0)  {  n/=i;  ans*=i-1;  while(n%i==0)  {  n/=i;  ans*=i;  }  }  }  if(n>1)  ans*=n-1;  return ans;  
}  
int main()  
{  int n;  while(scanf("%d",&n),n)  {  printf("%d/n",n-1-euler(n));  }  return 0;  
}  下面是另外一种（筛选法）[c-sharp] view plain copy
#include <iostream>  
using namespace std;  
#define N 100005  
#define ll __int64  ll eule[N];  
int p[N][15];  
int num[N];  void init()  
{     int i,j;  eule[1]=1;    for(i=2;i<N;i++)//筛选法得到数的素因子及每个数的欧拉函数值         {  if(!eule[i])              {             for(j=i;j<N;j+=i)                  {                 if(!eule[j])                      eule[j]=j;                eule[j]=eule[j]*(i-1)/i;                  p[j][num[j]++]=i;                 }             }         eule[i]+=eule[i-1];   }  
}  

这篇关于欧拉函数的求法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---