一文读懂欧拉函数

来自：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、数据库、运维等。