素数&欧拉函数

素数表

const int maxN找[1,maxN)内的素数

int prime[int I]第I个素数

const int maxN=1e5+5;

int prime[maxN];

bool mark[maxN];

void init_prime()

{

    int cnt=0;

    for(int i=2;i<maxN;++i)

    {

        if(!mark[i])prime[++cnt]=i;

        for(int j=1;j<=cnt&&prime[j]*i<maxN;++j)

        {

            mark[prime[j]*i]=true;

            if(i%prime[j]==0)break;

        }

    }

}

---

欧拉函数表（同时得到素数表）

const int maxn同上

int prime[int j]同上

int phi[int j]欧拉函数

const int maxN=1e5+5;

int prime[maxN],phi[maxN];

bool mark[maxN];

void init_prime_phi()

{

    phi[1]=1;

    int cnt=0;

    for(int i=2;i<maxN;++i)

    {

        if(!mark[i]){prime[++cnt]=i;phi[i]=i-1;}

        for(int j=1;j<=cnt&&prime[j]*i<maxN;++j)

        {

            mark[prime[j]*i]=true;

            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}

            else phi[i*prime[j]]=phi[i]*(prime[j]-1);

        }

    }

}