筛法

埃氏筛

\(O(n\log\log n)\)

inline void primes(int n)
{
    memset(v,0,sizeof v);
    for(int i = 2;i <= n;i++){
        if(v[i]) continue;
        p.push_back(i);
        for(int j=i;j<=n/i;j++) v[j*i]=1;
    }
}

线性筛

\(O(n)\)

inline void xxs(int n)
{
    memset(v,0,sizeof v);
    m=0;
    for(int i = 2;i <= n;i++){
        if(!v[i]) p[++m]=i;
        for(int j = 1;j <= m;j++){
            if(p[j]*i>n) break;
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}

欧拉函数

\(\varphi(x)\) 表示小于等于 \(x\) 的正整数中与 \(x\) 互质的数的数量。规定 \(\varphi(1) = 1\) 。

性质

若 \(p\) 为质数， \(\varphi(p^n) = p^{n-1}(p-1)\)
若 \(a|x\) ，\(\varphi(ax)=a\varphi(x)\)
若 \(a,b\) 互质，\(\varphi(a)\varphi(b)=\varphi(ab)\)

性质 \(1\) 证明：

小于等于 \(p^n\) 的正整数中，不与 \(p^n\) 互质的只有 \(p,2p,3p,...,p^{n-1}p\) 共 \(p^{n-1}\) 个数，\(\varphi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)\) 。

求欧拉函数

单次求欧拉函数

设 \(p_i\) 表示 \(x\) 的质因数。

\[\varphi(x)=x\prod\dfrac{p_i-1}{p_i} \]

将 \(x\) 质因分解即可，时间复杂度 \(O(\sqrt n)\) 。

证明：

\[x=\prod {p_i}^{k_i} \]

由性质 \(3\) 可得：

\[\varphi(x)=\prod\varphi({p_i}^{k_i}) \]

由性质 \(2\) 可变为：

\[\begin{aligned}\varphi(x) & =\prod {p_i}^{k_i-1}(p_i-1)\\& =\prod {p_i}^{k_i}\dfrac{1}{p_i}(p_i-1)\end{aligned} \]

将 \({p_i}^{k_i}\) 提出来得 \(x\) ，即：

\[\varphi(x)=x\prod\dfrac{p_i-1}{p_i} \]

求 1~n 的欧拉函数

与线性筛相结合。

若 \(x\) 为质数，\(\varphi(x)=x-1\) 。（性质 \(1\) ）
否则对于 \(x\) 的质因数 \(p\) ，\(\varphi(x)=\begin{cases}p\cdot\varphi\left(\dfrac{x}{p}\right) \ \ \ \ \ \ \ \ \ \left(p|\dfrac{x}{p}\right)\ \ \ \ 性质 2\\\varphi(p)\cdot\varphi \left(\dfrac{x}{p}\right) \ \ \ \left(p\nmid\dfrac{x}{p}\right)\ \ 性质3\end{cases}\)

时间复杂度 \(O(N)\)

void primes(int n)
{
    memset(v,0,sizeof v);
    m=0;
    phi[1]=1;
    for(int i = 2;i<= n;i++){
        if(!v[i]) p[++m]=i,phi[i]=i-1;
        for(int j = 1;j <= m;j++){
            if(p[j]*i>n) break;
            v[i*p[j]]=1;
            if(i%p[j]==0) {phi[i*p[j]]=p[j]*phi[i];break;}
            else phi[i*p[j]]=phi[p[j]]*phi[i];
        }
    }
}