欧拉函数模板

c #include<stdio.h> int oula(int n)//欧拉函数 用于 求得 小于正整数 n 且与 n {int res=n; int i; for(i=2;i*i<=n;i++) { if(n%i==0)res=res/i*(i-1); while(n%i==0)n/=i;

}
if(n>1)res=res/n*(n-1);

  return res;

}

int main()
{
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
printf("%d ",i) ;
printf("\n");
for(i=1;i<=n;i++)//非线性欧拉
printf("%d ",oula(i)) ;

printf("\n");
int a[100];a[1]=1;
for(i=2;i<=n;i++)//初始 线性 欧拉函数
a[i]=i;
for(i=2;i<=n;i++)
{
if(a[i]!=i)continue;
for(j=i;j<=n;j+=i)//筛选掉所有含此数
a[j]=a[j]/i*(i-1);

}
for(i=1;i<=n;i++)
printf("%d ",a[i]) ;
return 0;
}