欧拉函数模板-----------C语言—菜鸟级

举报
Fivecc 发表于 2022/08/05 23:40:14 2022/08/05
【摘要】 #include<stdio.h> int oula(int n)//欧拉函数 用于 求得 小于正整数 n 且与 n {int res=n; int i; for(i=2;...
#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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。