筛法求欧拉函数

证明：

因为欧拉函数的求解只与质数的值有关而与质数的个数无关
所以1：当i%primes[j]!=0时，即primes[j]不是i的质数
所以oula[primes[j]*i]=oula[i]*(primes[j]-1)  //一个质数的欧拉函数是其数值减一
    2：当i%priems[j]==0时，即primes[j]是i的最小质数
即 1-1/priems[j]已经再oula[i]中出现过了，所以就不用再×了，所以
oula[primes[j]*i]=oula[i]*primes[j];

代码：

#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int st[N];
int primes[N];
int oula[N];
ll ular(int n){
    int k=0;
    oula[1]=1;
    for(int i=2;i<=n;i++){

        if(st[i]==0){
            primes[k++]=i;
            oula[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0){
                oula[i*primes[j]]=oula[i]*primes[j];
                break;
            }
            oula[i*primes[j]]=oula[i]*(primes[j]-1);
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=oula[i];
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    cout<<ular(n);

    return 0;
}

欧拉定理：