欧拉函数

落日映苍穹つ 2022-05-16 07:58 272阅读 0赞

### 定义 ###

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。

### 通式 ###

![70][]，其中![\\prod][prod]是累积的意思（对比![\\sum][sum]是累加），p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1。

注意：每种质因数只一个。 比如12=2\*2\*3那么φ（12）=12\*（1-1/2）\*(1-1/3)=4。

此通式还可以化简为 ![\\varphi \\left ( x \\right )=x\\prod\_\{i=1\}^\{n\}\\left ( 1-\\frac\{1\}\{p\_\{i\}\} \\right )][varphi _left _ x _right _x_prod_i_1_n_left _ 1-_frac_1_p_i_ _right]

![=\\prod\_\{i=1\}^\{n\}\\frac\{x\}\{p\_\{i\}\}\\left ( p\_\{i\}-1 \\right )][prod_i_1_n_frac_x_p_i_left _ p_i_-1 _right]

### 特殊性质 ###

1.当n为奇数时，![70 1][] 。

2.若n为质数，则 ![70 2][]。

3.若m,n互质， ![70 3][]。

4.若n是质数p的k次幂， ![f9198618367adab410da834e8cd4b31c8701e4b1.jpg][] ，因为除了p的倍数外，其他数都跟n互质。

### 代码实现 ###

1.用公式直接求一个数的欧拉函数值

int Phi(int x){  //求x的欧拉函数值
        if (x<=3) return x-1;
        int ret=x;
        for (int i=2; i*i<=x; i++) if (x%i==0){
            while (x%i==0) x/=i;//这是要去掉x中i的倍数，这些i的倍数都不是质数
            ret=ret/i*(i-1);//利用公式计算
        }
        if (x>1) ret=ret/x*(x-1);//若x>1，则说明此时的x是初始x的质因数，因此还需要在使用一次公式
        return ret;
    }

2.利用筛法求大范围内的所有数的欧拉函数值（打表）

/*
    特性 :
    1.若a为质数,phi[a]=a-1;
    2.若a为质数,b mod a=0,phi[a*b]=phi[b]*a
    3.若a,b互质,phi[a*b]=phi[a]*phi[b](当a为质数时,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
    */
    int m[n],phi[n],p[n],nump;
    //m[i]标记i是否为素数,0为素数,1不为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函数
    int make()
    {
            phi[1]=1;
        for (int i=2;i<=n;i++)
        {
            if (!m[i])//i为素数
            {
                p[++nump]=i;//将i加入素数数组p中
                phi[i]=i-1;//因为i是素数,由特性1得知    
            }    
            for (int j=1;j<=nump&&p[j]*i<n;j++)  //用当前已的到的素数数组p筛,筛去p[j]*i
            {
                m[p[j]*i]=1;//可以确定i*p[j]不是素数 
                if (i%p[j]==0) //看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质 
                {
                    phi[p[j]*i]=phi[i]*p[j]; //特性2
                    break;
                }
                else phi[p[j]*i]=phi[i]*(p[j]-1); //互质,特性3其,p[j]-1就是phi[p[j]]   
            }
        }
    }

### 提示 ###

欧拉函数属于积性函数  
积性函数: 对于正整数n的一个算术函数f(n),若f(a)=1,且当a,b互质时f(a\*b)=f(a)\*f(b),在在数论上就称它为积性函数。  
完全积性函数: 对于一个积性函数f(n),若即使a,b不互质(对于任意的a,b)也有f(a\*b)=f(a)\*f(b)则称它为完全积性函数。  
对于这种奇性函数,一般都可以用这种筛法来打表。

[70]: https://img-blog.csdn.net/20180817202841245?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTgxNzcy/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[prod]: https://private.codecogs.com/gif.latex?%5Cprod
[sum]: https://private.codecogs.com/gif.latex?%5Csum
[varphi _left _ x _right _x_prod_i_1_n_left _ 1-_frac_1_p_i_ _right]: https://private.codecogs.com/gif.latex?%5Cvarphi%20%5Cleft%20%28%20x%20%5Cright%20%29%3Dx%5Cprod_%7Bi%3D1%7D%5E%7Bn%7D%5Cleft%20%28%201-%5Cfrac%7B1%7D%7Bp_%7Bi%7D%7D%20%5Cright%20%29
[prod_i_1_n_frac_x_p_i_left _ p_i_-1 _right]: https://private.codecogs.com/gif.latex?%3D%5Cprod_%7Bi%3D1%7D%5E%7Bn%7D%5Cfrac%7Bx%7D%7Bp_%7Bi%7D%7D%5Cleft%20%28%20p_%7Bi%7D-1%20%5Cright%20%29
[70 1]: /images/20220516/6a27d6528d95435ba481689694159402.png
[70 2]: /images/20220516/84bfb9753614427eb60421e9906092d4.png
[70 3]: /images/20220516/d6a216fc4b2846ed9aadefb65a5e4101.png
[f9198618367adab410da834e8cd4b31c8701e4b1.jpg]: https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D211/sign=8a21a419ac18972ba73a07cbd7cd7b9d/f9198618367adab410da834e8cd4b31c8701e4b1.jpg