欧拉函数
#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);
}
0