歐拉函數（模板）
標簽： 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];   }  
}  

總結

以上是生活随笔為你收集整理的欧拉函数的求法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。