欧拉函数模板-----------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;
  }

/*void xxoula()
{int i,j;
	px[1]=1;
	for(i=2;i<=n;i++)
	{
		if(!mk[i])px[i]=i-1,px[++t]=i;
		for(j=1;j<=t;j++)
		{ int x=px[j];
		 if(i*x>n)break;
		 mk[i*x]=1;
		 if(i%x==0){px[i*x]=px[i]*x;break;}
		  else px[i*x]=px[i]*p[x];
		}
	}
}
int main()
{
int i,n,t,ans=0,m;
scanf("%d%d",&n,&m);
for(i=1;i*i<=n;i++)///开根号将复杂度 
{
	if(n%i==0)
	{ if(i>=m)ans+=oula(n/i);
	 if(i*i!=n&&n/i>=m)ans+=oula(i);
	}
}
printf("%d",ans); 

return 0;
} */
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;
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80238010