线性筛素数 欧拉函数

复杂度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 ;
}
全部评论

相关推荐

05-09 13:22
门头沟学院 Java
点赞 评论 收藏
分享
04-25 18:13
五邑大学 Java
后来123321:大二两段实习太厉害了,我现在大二连面试都没有
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务