微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

一文读懂欧拉函数

2018-01-13 10:00 算法与数据结构

来自:ivy-end

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


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


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




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


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


代码如下:


#include

using namespace std;

const int MAX = 1024;

int N;

int p[MAX], phi[MAX];

int main()

{

    cin >> N;

    for(int i = 1; i <= N; i++)// 初始化

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

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

    for(int i = 2; i <= N; i++)// 筛素数

    {

        if(p[i])

        {

            for(int j = i * i; j <= N; j += i)

            { p[j] = 0; }

        }

    }

    for(int i = 2; i <= N; i++)// 求欧拉函数

    {

        if(p[i])

        {

            for(int j = i; j <= N; j += i)// 处理素因子p[i]

            {

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

            }

        }

    }

    cout << "Primes: " << endl;

    for(int i = 1; i <= N; i++)

    { if(p[i]) { cout << i << " "; } }

    cout << endl;

    cout << "Euler Phi Function: " << endl;

    for(int i = 1; i <= N; i++)

    { cout << phi[i] << " "; }

    return 0;

}


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


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


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


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


代码如下:


#include

#include

using namespace std;

typedef unsigned long long ull;

ull N;

ull phi(ull x);

int main()

{

    cin >> N;

    cout << phi(phi(N)) << endl;

    return 0;

}

ull phi(ull x)

{

    ull ans = x;

    ull m = (ull)sqrt(x);

    for(ull i = 2; i <<= m; i++)

    {

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

        {

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

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

            { x /= i; }

        }

    }

    if(x > 1)// 防质数

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

    return ans;

}



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

●输入m获取文章目录

推荐↓↓↓

Python编程

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

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

 
算法与数据结构 更多文章 3 个月如何从小白到 Python 高手?清华博士带你入门带你飞! 火爆全球的区块链到底是怎么一回事?一文带你看懂 这位所有程序员心中的大神今天80岁了 权威报告:2018 年数据人才紧缺,现在入行恰逢其时 图解堆排序
猜您喜欢 怎样成为一个优秀的PHP开发者? 活动 | 深圳 Gopher Meetup 分享交流 8点1氪:劫匪利用Pokémon Go定位作案;马云称SEC调查有利于外界更好的了解阿里;全聚德董事长总经理董秘集体辞职 [精校版]Using Swift with Cocoa and Objective-C--将ObjC代码迁至Swift 服务化体系之-兼容性与版本号