欧拉函数模板-----------C语言—菜鸟级
【摘要】
#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;
}
文章来源: fivecc.blog.csdn.net,作者:Five-菜鸟级,版权归原作者所有,如需转载,请联系作者。
原文链接:fivecc.blog.csdn.net/article/details/80238010
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)