这种方法判断一个数是不是合数依靠的是其最大的素因子而不是最小的。
与欧拉筛不同，我们先开一个数组储存已经判断过的数，包括素数和合数；

bool searcher[maxn]; int sushu[maxn]; int ypd[maxn];
//ypd即已判断。
//储存素数的数组应该可以开的更小，
//但是我不知道应该开多小就直接maxn了

这个数组是以后用的妙妙工具。
然后我们从2开始。
由于没有比2小的素数，所以所谓的最大的质因数就是2，也就是说能够被标记的只有2的幂；
然后我们把这一坨数全都放进ypd[]。
然后让我们思考一个问题：如果把一个数最大的质因数全丢拿走，剩下的是什么？
是一个所有质因数都小于那个我们拿走的最大质因数的数（你不是搁这搁这嘛）
然后我们发现，对于任意质数，所有的对它来说的这类数都被放在了ypd[]里面。
那么我们可以把ypd[]内的所有数依次乘这个质数，并且只要乘积小于判断上限就把这个乘积放进ypd[]

对于纯质数的幂，我们可以考虑在初始化的时候在一开头放一个1
差不多就这样吧，放一下代码：

void ini(int m)//m是判断的上限，以下同理 
{
	ypd[0]=1;
	for(int i=1;i<=m;i++)
	{
		searcher[i]=false;
	}	
}
void treat(int m)
{
	if(m<=1) return ; int pointer1=0;int pointer2=1;
	int treater_max=m/2+1; long long mtper;
	for(int num=2;num<=treater_max;num++)
	{
		if(searcher[num]) continue;
		sushu[pointer1++]=num; 
		for(int i=0;i<pointer2;i++)
		{
			mtper=ypd[i]*num;
			if(mtper<m) 
			{
				ypd[pointer2++]=mtper;
				searcher[mtper]=true;
			}
		} 
	}
	for(;m>treater_max;treater_max++)
	{
		if(!searcher[treater_max]) sushu[pointer1++]=treater_max; 
	}
	return ; 
}

每个范围以内的数都只被判断一次，所以是线性的

但是对范围外的数的判断造成了巨大的时间上的浪费，储存判断过的数造成了巨大的空间上的浪费（使得空间复杂度直接翻倍并且让我喜提5个re于某模板题），所以就当灌水吧()
顺便，蹲一个大佬优化()