一文读懂欧拉函数

来自:ivy-end

http://www.ivy-end.com/archives/1021

欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。又称φ函数、欧拉商数。

下面介绍欧拉函数的几个性质:

我们根据这几个性质就可以求出欧拉函数。

基本思路是首先置φ(N)=N,然后再枚举素数p,将p的整数倍的欧拉函数φ(kp)进行如下操作。

代码如下:

#include

usingnamespacestd;

constintMAX=1024;

intN;

intp[MAX],phi[MAX];

intmain()

{

for(inti=1;i

{p[i]=1;phi[i]=i;}

p[1]=;// 1不是素数

for(inti=2;i

{

if(p[i])

{

for(intj=i*i;j

{p[j]=;}

}

}

for(inti=2;i

{

if(p[i])

{

for(intj=i;j

{

phi[j]=phi[j]/i*(i-1);// 先除后乘,防止中间过程超出范围

}

}

}

cout

for(inti=1;i

{if(p[i]){cout

cout

cout

for(inti=1;i

{cout

return;

}

以上是关于欧拉函数的求法,对于它的应用,这里暂且介绍一个——求解原根的个数。

对于原根的定义,我们可以这样来叙述:

若存在一个实数a,使得( a^i ) mod N,a∈的结果各不相同,我们就成实数a为N的一个原根。

原根的个数等于φ(φ(N))。这样我们就可以很方便的求出原根的个数。

代码如下:

#include

#include

usingnamespacestd;

typedefunsignedlonglongull;

ullN;

ull phi(ullx);

intmain()

{

cout

return;

}

ull phi(ullx)

{

ullans=x;

ullm=(ull)sqrt(x);

for(ulli=2;i

{

if(x%i==)// 求素因子

{

ans=ans/i*(i-1);// 运用通项求解欧拉函数

while(x%i==)// 每个素因子只计算一次

{x/=i;}

}

}

if(x>1)// 防质数

{ans=ans/x*(x-1);}

returnans;

}

●本文编号558,以后想阅读这篇文章直接输入558即可

●输入m获取文章目录

推荐↓↓↓

Python编程

更多推荐《18个技术类微信公众号》

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180113B05HQG00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券