欧拉函数学习笔记

· · 个人记录

一.引入

任意给定正整数 n ，问在小于等于 n 的正整数之中，有多少个与 n 互质？

计算这个值的函数叫欧拉函数，用 \varphi(n) 表示。

二.定义

在数论中，对于正整数 n ，\varphi(n) 是小于 n 的正整数中与 n 互质的数的数目。特别的 ， \varphi(1)= 1 。

三.性质

1.欧拉函数是积性函数，但不是完全积性函数。

对于素数 p , \varphi(p)=p-1 , 对于两个素数 p,q , \varphi(pq)=(p-1)(q-1) 。

2.当 n>2 时 ， \varphi(n)\equiv0\pmod{2}

3.设 n≥1 则有 \sum\varphi(d)=n ，其中 d | n ， d>0 。

四.计算方法

通式：\varphi(x)=x\prod_{i=1}^n(1-\frac{1}{p_i})

1.埃氏筛

基本思想是对于每个 ≥ 2 的整数，把它们的非平凡倍数标记为不是质数。 我们从小到大考虑每个 ≥ 2 的整数，如果它没有标记则它是质数。 如果它是质数，我们把它的所有非平凡倍数标记为不是质数。 复杂度是 n\sum \frac{1}{prime} = O(n log log n)

一个常数优化：对于一个质数 p ，我们只用标记 ≥ p^2 的倍数。这并不改变复杂度。

代码如下：

void get_euler(int n){
    for(int i=1;i<=n;i++){
        e[i]=i;
    }
    for(int i=2;i<=n;i++){
        if(e[i]==i){
            for(int j=i;j<=n;j+=i){
                e[j]=e[j]/i*(i-1);
            }
        }
    }
}

2.欧拉筛

也被称为线性筛 (因为复杂度是线性)。 考虑从另一个方向优化标记，也就是对所有数考虑乘一个质数得到的新数。 由唯一分解定理，每个 ≥ 2 的整数可以唯一被分解为形如 \prod_{i=1}^kp_i 的形式，其中 p1 ≥ p2 · · · ≥ pk ， k ≥ 1 。 于是我们考虑标记的时候只在当前的 p 末尾加新的 p_{k+1} ，即我们保证枚举的质数 q ≤ p_k 。 这样每个合数只会被枚举出来一次，因此复杂度是 O(n) 。

代码如下

void get_euler(int n){
    e[1]=1;
    for(int i=2;i<=n;i++){
        if(!val[i]){
            prime[++num]=i;
            e[i]=i-1;
        }
        for(int j=1;j<=num&&prime[j]*i<=n;j++){
            val[i*prime[j]]=1;
            if(i%prime[j]==0){
                e[i*prime[j]]=e[i]*prime[j];
                break;
            }
            else e[i*prime[j]]=e[i]*e[prime[j]];
        }
    }
}