线性筛素数 欧拉函数

复杂度O(n)

bool v[100000010];
int prime[100010],tot=0;
void init(int n)
{
	v[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])	prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0)	break;
		}
	}
	return ;
}

模版：https://www.luogu.com.cn/problem/P3383

bool v[maxn];
int prim[maxn],phi[maxn],tot=0;
void eular()
{
	v[1]=1;
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
			prim[++tot]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tot&&i*prim[j]<=n;j++)
		{
			v[i*prim[j]]=1;
			if(i%prim[j]==0)
			{
				phi[i*prim[j]]=phi[i]*prim[j];
				break;
			}
			phi[i*prim[j]]=phi[i]*(prim[j]-1);
		}
	}
	return ;
}