数论 欧拉筛和欧拉函数基础(Sieve of Euler and Phi)

· · 个人记录

一.欧拉筛求素数

1.简介

欧拉筛可以线性求出所有素数

与其它找质数的方法比起来速度会有很大的提升

而且还可以解决如找所有数的质因数之类的问题

2.原理

一个合数c最小的质因数a是唯一的 最大的因数b

而且有：c=a\times b

3.实现方法

由于这个方法是线性的

那么也就意味着所有合数会且只会被找到一次

而上面的引理很巧的就是唯一的

因此我们就要使一个合数只会被最大的因数找到

而实现的方法十分的简单

每次找到一个数拓展的时候加上一句:

if(i%f[j]==0) break;//i是当前的数 f[j]是质数

4.证明

我们只需要从正反两面证明这个结论:

i.f_j之前的所有质数(包括f_j) s都是s\times i的最小质因数

由于f_j是i第一个可以整除的质数

这也就意味着f_j是i的最小质因数

换言之s比i最小的质因数还小

那在新的数里面s必然就是最小的质因数

而i就是s\times i中最大的因数

ii.f_j之后的所有数l都不是l\times i的最小质因数

其实和上面一样

由于f_j已经是最小质因数了

所以l\times i=f_j\times (l\times i \div f_j)

即可以写成原理的式子通过l\times i \div f_j这个数推到

总结

按照这个方法我们可以让使得每一个合数只能通过最大的因数推到

因此我们就可以实现O(n)复杂度找出所有的合数

那么剩下的必然就是质数了

code

for(register int i=2;i<=n;i++){
    if(!a[i]) f[++f[0]]=i;//ai是标记是否为素数
    for(register int j=1;j<=f[0];j++){
        if(1ull*i*f[j]>n) break;//当然每次求的新合数不超过n
        a[f[j]*i]=1;//合数打上标记
        if(i%f[j]==0) break;刚刚推得的结论
    }
}

注意f_j是包括在s里的 即先打标记再判断

5.例题

素数个数

【题目描述】

求 1,2,......N(N<=10^8) 中素数的个数。

【输入格式】

一行一个整数N

【输出格式】

一行一个整数表示素数的个数

样例输入

10

样例输出

4

没啥好说的

直接筛出N以内所有质数再加起来

code

#include<cstdio>
int n,f[5761500],ans;//f:所有质数
bool a[100000005];//标记合数
int main(){
    scanf("%d",&n);
    a[1]=1;
    for(register int i=1;i<=n;i++){
        if(!a[i]) f[++f[0]]=i,ans++;
        for(register int j=1;j<=f[0];j++){
            if(1ull*f[j]*i>n) break;
            a[f[j]*i]=1;
            if(i%f[j]==0) break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

二.欧拉函数

1.简介

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。

此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、\phi函数、欧拉商数等。

从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明 （转自百度百科）

2.定义

例如$\phi (1)=1

3.一些简单的特殊性质和式子

i.若n为质数 \phi(n)=n-1

这个挺好理解的

如果一个数是质数 那么前面的所有数必然和它互质

ii.欧拉函数是积性函数 \;即若m,n互质 则\phi(m\times n)=\phi (n)\times \phi (m)

不妨设存在两个互质数m和n

我们把1至mn的所有数做成一个m\times n的矩阵

\left[ \begin{matrix} 1 & 2 & 3&\cdots & n\\ n+1 & n+2 & n+3&\cdots & 2n\\ 2n+1 & 2n+2 & 2n+3 & \cdots & 3n\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ n(m-1)+1 & n(m-1)+2 & n(m-1)+3 & \cdots & nm \end{matrix} \right]

我们知道在前n个数中与n互质的数有\phi(n)个

而且我们也知道如果a与n互质 那么a+n必然与n互质

于是在矩阵中与n互质的数刚好是零散的\phi(n)列

同样的与m互质的数有零散的\phi(m)行

我们知道一个数要想与mn互质要与m和n都互质

即互质的数既在那\phi(n)列中 又在\phi(m)行中

那么与mn互质的数合在一起就是\phi(m)行\phi(n)列的矩形

因此\phi(nm)=\phi(n)\times \phi(m)

iii.若n为质数 那么\phi(n^m)=(n-1)\times n^{m-1}

证明

还是上面的想法

我们要求的n^m其实就是一个n列n^{m-1}行的矩阵

因为n为质数

所以所有与n^m互质的数都与n互质 反之也成立

而矩阵中不与n互质的数只有第n列（都是n的倍数）

那么剩下的n-1列必然都是与n互质

因此\phi(n^m)=(n-1)\times n^{m-1}

也可以变式为\phi(n^m)=n^m-n^{m-1}

iv.\sum_{d|n} \phi(d)=n

证明

我们先从最特殊的n=a^b,a是质数的情况开始推起

\begin{aligned} \sum_{d|a^b} \phi(a^b)&=\phi(a^b)+\phi(a^{b-1})+ \cdots+\phi(1)\\ &=a^b-a^{b-1}+a^{b-1}-a^{b-2}+\cdots+a-1+1\\ &=a^b \end{aligned}

由于我们已经证明过积性了

那么我们把n拆成若干个质因数相乘

\begin{aligned} n&=\prod a^b\\ &=\prod \sum_{d|a^b}\phi(d)\\ \end{aligned}

我们发现每一个因数在这个式子里一定会且只会被算一次

而非因数不会在这个式子里被算到

因此我们可以认为这就是算n的所有因子的\phi的和

因此有:

n=\sum_{d|n} \phi(d)

4.通式(可以先通式再推积性 也可以先积性再推通式)

不妨假设P为n所有质因数的集合

那么就有

\phi (n)=n\times \prod(1-\dfrac{1}{p_i})

证明

我们先把n写成质因数相乘的形式:

n=\prod p_i^{q_i}

由于p_i都是互质的

因此我们可以根据积性和公式iii开始推式子:

\begin{aligned} \phi(n)&=\prod \phi(p_i^{q_i})\\ &=\prod(p_i-1)\times (p_i^{q_i-1})\\ &=\prod(1-\frac{1}{p_i})\times p_i^{q_i}\\ &=\prod(1-p_i) \times \prod p_i^{q_i}\\ &=n\times \prod(1-\frac{1}{p_i}) \end{aligned}

这个通式就是求单个数的欧拉函数的式子

code

inline int phi(a){
    int ans=a;//ans就是欧拉函数 一开始是a 
    for(register int i=2;i*i<=a;i++){
        if(a%i==0) ans=ans/i*(i-1);//根据通式 有一个质因数就乘上(1-1/p) 
        while(a%i==0) a/=i;//除去所有的这个质因数 保证没有合数会被取出 
    }
    if(a>1) ans=ans/a*(a-1);//最后有可能只剩下某个质因数而且指数为1 那么n就是那个质因数 
    return ans;
}

但是如果要求一段数的欧拉函数就要请出我们的欧拉筛了

三.欧拉筛求欧拉函数

我们在一处讲了欧拉筛

欧拉筛之所以叫作欧拉筛是因为它不仅仅可以很快地求素数

而且还可以在求素数的同时求出所有数的欧拉函数

1.原理

我们在用欧拉筛的时候

每次找到一个合数n都是从它的最小质因数a和最大因数b推来的

i.如果b\%a\neq 0!

那么就意味着b和a互质

根据积性可以推得:

\phi(n)=\phi(a) \times \phi(b)=\phi(a)\times (b-1)

ii.如果b\%a =0

我们还是用矩阵的方式想 有一个b列a行的矩阵

由于b是a的倍数那么我们就只用考虑与b互质的数即可

那么每一行与b互质的数有\phi(b)个

一共有a行

\phi(n)=\phi(a) \times b

2.代码

我们只需要在求质数的代码上作小许修改

for(register int j=1;j<=f[0];j++){
    if(f[j]*i>n) break;
    a[f[j]*i]=1;
    if(i%f[j]==0){
        phi[f[j]*i]=phi[i]*f[j];//第二种情况
        break;
    }
    else phi[f[j]*i]=phi[i]*(f[j]-1);//第一种情况
}

3.例题

GCD SUM.

【题目描述】

求

\sum_{i=1}^n \sum_{j=1}^n gcd(i,j)

【输入格式】

一行一个整数n(n<=10^5)

【输出格式】

一行一个整数表示答案

样例输入

2

样例输出

5

我们不妨先来推一下式子

\begin{aligned} \sum_{i=1}^n \sum_{j=1}^n gcd(i,j)&=\sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(i,j)} \phi(d)\\ &=\sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^n [d|i]\times [d|j]\times \phi(d)\\ &=\sum_{d=1}^n \phi(d) \sum_{i=1}^n \sum_{j=1}^n [d|i]\times [d|j]\\ &=\sum_{d=1}^n \phi(d) \lfloor \frac{n}{d} \rfloor ^2 \end{aligned}

于是我们只需要求出所有的\phi(d)

这个就是欧拉筛的模板题

code

#include<cstdio>
const int maxn=100005;
long long n,f[maxn],phi[maxn],ans=0;
bool a[maxn];
int main(){
    scanf("%lld",&n);
    phi[1]=a[1]=1;
    for(register int i=2;i<=n;i++){//欧拉筛找欧拉函数模板
        if(!a[i]){
            f[++f[0]]=i;
            phi[i]=i-1;
        }
        for(register int j=1;j<=f[0];j++){
            if(f[j]*i>n) break;
            a[f[j]*i]=1;
            if(i%f[j]==0){
                phi[f[j]*i]=phi[i]*f[j];
                break;
            }
            else phi[f[j]*i]=phi[i]*(f[j]-1);
        }
    }
    for(register int i=1;i<=n;i++){//统计答案
        ans+=phi[i]*(n/i)*(n/i);
    }
    printf("%lld\n",ans);
    return 0;
}

四.后记

敲了一个星期多终于搞完了

和欧拉函数有关的知识点及奇奇怪怪的性质会另外写一篇

Finally，谢谢大家

参考资料:

知乎问题：如何证明欧拉函数是积性函数

欧拉函数 百度百科

@DICalculus 的Blog