注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C语言求欧拉函数模板

OC/C/C++ 水墨上仙 1305次浏览 已收录 手机上查看

欧拉函数

E(n)表示小于n的所有正数,与n互质的数的个数

1 当p为素数时,显然E(p)= p-1

2 当n=p^k (p为素数)时,E(p^k)=p^k-p^(k-1)

证明:小于n的数一共有p^k-1个,其中不与p互质的有p*1,p*2,p*3,…p*(p^(k-1)-1)(显然有p^(k-1)-1个),则E(n)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1);

3 任何一个整数n都可以表示为n=(p1^a1)*(p2^a2)*…*(pn^an)

若ab互质,E(ab)=E(a)*E(b),欧拉函数为积性函数

E(n)=E(p1^a1)*E(p2^a2)*…*E(pn^an)

=(p1^a1-p1^(a1-1))*(p2^a2-p2^(a2-1))*…*(pn^an-pn^(an-1))

=(p1^a1*p2^a2*..*pn^an)*((1-1/p1)*(1-1/p2)*…*(1-1/pn))

=n*(1-1/p1)*(1-1/p2)*…*(1-1/pn)

4 E(p^k)=p^k-p^(k-1)=(p-1)*p^(k-1)

E(p^(k-1))=p^(k-1)-p^(k-2)=(p-1)*p^(k-2)

当k=1时,E(p)=p-1

当k>1时,E(p^k)=E(p^(k-1))*p

由上式,当p为素数时

若p是n的约数,E(n*p)=E(n)*p

否则,E(n*p)=E(n)*E(p)=E(n)*(p-1)

转自:http://blog.csdn.net/yyf573462811/

//求n的欧拉函数值,模板



#include"stdio.h"
int phi(int n)
{
	int i;
	int ans;
	ans=1;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ans*=(i-1);
			n/=i;
			while(n%i==0)
			{
				ans*=i;
				n/=i;
			}
		}
	}
	if(n!=1)ans*=n-1;
	return ans;
}
int main()
{
	int n;
	while(scanf("%d",&n)!=-1)
		printf("%d\n",phi(n));
	return 0;
}


喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……