素数欧拉筛法

线性筛素数

int pnum=0;
int pa[maxn];
bool pvis[maxn];
void prime_init()
{
	memset(pvis,0,sizeof(pvis));
	FOR(i,2,MAX)
	{
		if (!pvis[i])
		{
			pvis[i]=1;
			pnum++;
			pa[pnum]=i;			
		}
		FOR(j,1,pnum) if (pa[j]*i<=MAX)
		{
			pvis[pa[j]*i]=1;
			if (i%pa[j]==0) break;
		}else break;
	}
}

莫比乌斯

int pnum=0;
int pa[maxn];
int mu[maxn];
bool pvis[maxn];
void mobius_init()
{
	mu[1]=1;
	memset(pvis,0,sizeof(pvis));
	FOR(i,2,MAX)
	{
		if (!pvis[i])
		{
			pvis[i]=1;
			pnum++;
			pa[pnum]=i;		
			mu[i]=-1;
		}
		FOR(j,1,pnum) if (pa[j]*i<=MAX)
		{
			pvis[pa[j]*i]=1;
			if (i%pa[j]==0)
			{
				mu[i*pa[j]]=0;
				break;
			}
			else
			{
				mu[i*pa[j]]=-mu[i];
//				break;
			}
		}
	}
}