素数&欧拉函数

素数表

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);
        }
    }
}