如何用线性筛法求欧拉函数

简介:

前几天做了一个关于欧拉函数的题,当时就做超时了,因为我是暴力做的,后来百度了一下 线性晒法求欧拉函数,所以今天就打算系统的看一下筛法求欧拉函数的问题,该算法在可在线性时间内筛素数的同时求出所有数的欧拉函数:

先介绍一下暴力的欧拉函数:

Eular(m) = m - (1-1/p1) - (1-1/p2) - ... - (1-1/pk)  [其中 p1, p2...pk为m的素因子]

int Eular(int m)
{
    int ret = m;
    for(int i=2; i<m; i++)
    {
        if(m%i == 0)
            ret -= ret/i;
        while(m%i == 0)
        {
            m /= i;
        }
    }
    if(m > 1)
        ret -= ret/m;
    return ret;
}

通过上述代码 我们发现它的复杂度还是挺高的~,所以在一些题目中可能不适合,会超时,所以我们就可以根据素数筛那样进行欧拉筛法:

要想求欧拉函数需要用到以下几个性质( p为素数 ):


1.  phi(p) == p-1 因为素数p除了1以外的因子只有p,所以与 p 互素的个数是 p - 1个


2. phi(p^k) == p^k - p^(k-1) == (p-1) * p^(k-1)

证明:

令n == p^k,小于 n 的正整数共有 p^k-1 个,其中与 p 不互素的个数共 p^(k-1)-1 个,它们是 1*p,2*p,3*p ... (p^(k-1)-1)*p

所以phi(p^k) == (p^k-1) - (p^(k-1)-1) == p^k - p^(k-1) == (p-1) * p^(k-1)。


3. 如果i mod p == 0, 那么 phi(i * p) == p * phi(i) (证明略)

举个例子:

假设 p = 3,i = 6,p * i = 18 = 2 * 3^2;

phi(3 * 6) == 18*(1-1/2)*(1-1/3) = 6

p * phi(i) = 3 * phi(6) = 3 * 6 * (1-1/2) *  (1-1/3) = 6 = phi(i * p) 正确


4. 如果i mod p != 0, 那么 phi(i * p) == phi(i) * (p-1) 

证明:

i mod p 不为0且p为质数, 所以i与p互质, 那么根据积性函数的性质 phi(i * p) == phi(i) * phi(p) 其中phi(p) == p-1

所以 phi(i * p) == phi(i) * (p-1).

再举个例子:

假设i = 4, p = 3, i * p = 3 * 4 = 12

phi(12) = 12 * (1-1/2) * (1-1/3) = 4

phi(i) * (p-1) = phi(4) * (3-1) = 4 * (1-1/2) * 2 = 4 = phi(i * p)正确


了解了这些性质之后 我们要做的就是就是写程序了,具体咋写呢,就让我们参考一下素数筛,然后就可以写啦。


My Code:

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e6+5;
bool flag[MAXN];///标记数组
int phi[MAXN];///欧拉函数值,i的欧拉函数值=phi[i]
int p[MAXN];///素因子的值
int cnt = 0;
void Get_phi()///筛法求欧拉函数
{
    cnt = 0;
    memset(flag, true, sizeof(flag));
    phi[1] = 1;
    for(int i=2; i<MAXN; i++)///线性筛法
    {
        if(flag[i])///素数
        {
            p[cnt++] = i;
            phi[i] = i-1;///素数的欧拉函数值是素数 - 1
        }
        for(int j=0; j<cnt; j++)
        {
            if(i*p[j] > MAXN)
                break;
            flag[i*p[j]] = false;///素数的倍数,所以i*p[j]不是素数
            if(i%p[j] == 0)///性质:i mod p == 0, 那么 phi(i * p) == p * phi(i)
            {
                phi[i*p[j]] = p[j] * phi[i];
                break;
            }
            else
                phi[i*p[j]] = (p[j]-1) * phi[i];///i mod p != 0, 那么 phi(i * p) == phi(i) * (p-1) 
        }
    }
}
int main()
{
    Get_phi();
    int m;
    while(cin>>m)///测试
    {
        cout<<phi[m]<<endl;
    }
    return 0;
}


练习题:


POJ 2478

HDU 2824



目录
相关文章
|
Java 调度
【Netty】主从反应器 ( Reactor ) 多线程模型
【Netty】主从反应器 ( Reactor ) 多线程模型
1273 0
【Netty】主从反应器 ( Reactor ) 多线程模型
|
C语言
【C语言程序设计——入门】基本数据类型与表达式(头歌实践教学平台习题)【合集】
这份文档详细介绍了编程任务的多个关卡,涵盖C语言的基础知识和应用。主要内容包括: 1. **目录**:列出所有关卡,如`print函数操作`、`转义字符使用`、`数的向上取整`等。 2. **各关卡的任务描述**:明确每关的具体编程任务,例如使用`printf`函数输出特定字符串、实现向上取整功能等。 3. **相关知识**:提供完成任务所需的背景知识,如格式化输出、算术运算符、关系运算符等。 4. **编程要求**:给出具体的代码编写提示。 5. **测试说明**:包含预期输入输出,帮助验证程序正确性。 6. 文档通过逐步引导学习者掌握C语言的基本语法和常用函数,适合初学者练习编程技能。
619 1
|
存储 传感器 消息中间件
[尚硅谷 flink] 状态管理 笔记
[尚硅谷 flink] 状态管理 笔记
723 0
|
资源调度 Kubernetes Java
10分钟入门Flink--架构和原理
相信你读完上一节的[《10分钟入门Flink--了解Flink》](https://mp.weixin.qq.com/s?__biz=MzI3OTA2MDQyOQ==&mid=2247483800&idx=1&sn=bcba92c8bc5081ec481f0ec01926ce26&chksm=eb4ccb3adc3b422cbae3bc577525f8611bcbb76b5ac4e5d395d5ee85f26897e27846b68bc4b8&token=2145213332&lang=zh_CN#rd)对Flink已经有初步了解了。这是继第一节之后的Flink入门系列的第二篇,本篇主要内容是
10分钟入门Flink--架构和原理
|
存储 消息中间件 缓存
NoSQL常用数据结构 LSM Tree 简介
NoSQL常用数据结构 LSM Tree 简介
909 0
|
机器学习/深度学习 存储 算法
素数判定 高级程序员才知道的那些事儿
其原理是这样的,设置一个标记数组,开始先把2的所有倍数都标记了,然后往后走发现3没有被标记,那3肯定是个素数,然后在标记数组中把所有3的倍数标记掉,然后发现4已经被标记了 跳过,到5……,直到标记完所有数字,那么剩下未标记的数字就是素数了,见上图,代码如下:
638 0
|
NoSQL Linux 应用服务中间件
计算机操作系统学习笔记(13)——⾼性能⽹络模式:Reactor 和 Proactor
计算机操作系统学习笔记(13)——⾼性能⽹络模式:Reactor 和 Proactor
609 0
|
SQL 存储 Oracle
【数据库05】玩转SQL的高阶特性 2
【数据库05】玩转SQL的高阶特性
|
算法 定位技术 索引
基于快速GeoHash,如何实现海量商品与商圈的高效匹配?
闲鱼团队就商品与商圈的匹配算法为我们展开详细解读。
2379 0