type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
欧拉函数
定义
在[1,n]的范围内所有与n互质的数字的个数。
我们用\varphi(n)来表示数字n的欧拉函数的值，例在[1,4]中与4互质的数字是：1 3，有两个，因此
性质
- 如果n是一个质数
- 如果n是一个质数，则存在n^k，则
- 积性函数：如果gcd(m,n)=1，则
计算公式
根据整数唯一分解定理：
即任何一个正整数都可以分解为若干个质数的a_i次幂的连乘积，其中s为质因子的个数。
因此：
因此我们可以得到欧拉函数的计算公式：
通俗来讲，n的欧拉函数值就是n对每个质因数分解所得到的质因数进行操作后的连乘积 然后再乘一个 n。
因此欧拉函数的值与n和他的质因子有关，与项数无关。
求某个数欧拉函数值
根据我们刚才得到的欧拉函数的计算公式，可以得到某个值的欧拉函数的值，我们可以使用试除法来计算
线性筛求区域内欧拉函数
如果 n 是质数，则
在线性筛中，一个合数一定是被他的最小质因子筛掉的。假设这个最小质因数是p_j，因此一定存在一个
此时会出现两种情况：
- 如果 i 能够被 p_j 整除，则 i 一定包含了 p_j 的所有质因子，因此我们可以得到：
- 如果 i 不能被 p_j 整除，则 i 与 p_j 一定是互为质数的，因此有以下式子：
并且通过这种线性筛，我们可以得到[1,n]范围内的所有的数字的欧拉函数。
最后代码如下：
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/oulafunc
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。