欧拉函数

欧拉函数

#include<stdio.h>
#include<stdlib.h>
int eular(int n)
{
    int ret=1,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n/=i,ret*=i-1;
            while(n%i==0) n/=i,ret*=i;
        }
    }
    if(n>1) ret*=n-1;
    return ret;
}
int main ()
{
      int n,s;
      scanf("%d",&n);
      s=eular(n);
      printf("%d",s);
      return 0;
}

(1)单独求欧拉函数

int eular(int n)
{
 int ret=1,i;
 for(i=2;i*i<=n;i++)
 if(n%i==0)
 {
  n/=i;  ret*=i-1;
  while(n%i==0) {n/=i;ret*=i;}
 }
 if(n>1) ret*=n-1;
 return  ret;
}

int euler(int x)
{
 int i, res=x,tmp=(int)sqrt(x*1.0)+1;
 for(i=2;i<tmp;i++)
 if(x%i==0)
 {
  res=res/i*(i-1);
  while(x%i== 0) x/=i;
 }
 if(x>1) res=res/x*(x-1);
 return res;
}

int eular(int n)
{
 int ret=n,i;
 for(i=2;i*i<=n;i++)
 if(n%i==0)
 {
  ret=ret/i*(i-1);
  while(n%i==0) n/=i;
 }
 if(n>1) ret=ret/n*(n-1);
 return ret;
}

先素数筛法在用欧拉函数(在此仅写其中的一个)

void eular(int n)
{
 int ret=n,i;
 for(i=1;i<=prime[0]&&prime[i]<=(int)sqrt(1.0*n);i++)
 if(n%prime[i]==0)
 {
  ret=ret/prime[i]*(prime[i]-1);
  while(n%prime[i]==0) n/=prime[i];
 }
 if(n>1) ret=ret/n*(n-1);
 return ret;
}

(2)递推求欧拉函数

const int  lmax=300000;
int PHI(int lmax)
{
 int i,j;
 for(i=1;i<=lmax;i++) phi[i]=i&1?i:i/2;
 for(i=3;i<=lmax;i+=2)
 if(phi[i])
 for(j=i;j<=lmax;j+=i) phi[j]=phi[j]/i*(i-1);
}