大概懂了一点，先贴一下代码，有空再深入研究，这应该算是数论的部分，不是很懂，但是要努力了，还有180多天noip，省一是目标！

#include<cstring>
#include<cstdio>
using namespace std;
int primelist[10000010];
bool vis[10000010];
int main()
{
	int n,size=0;
	scanf("%d",&n);
	memset(primelist,0,sizeof(primelist));
	memset(vis,true,sizeof(vis));
	vis[1]=false;
	for (int i=2;i<=n;i++)
	{
		if (vis[i])	primelist[++size]=i;
		for (int j=1;j<=size &&i*primelist[j]<=n;j++)
		{
			vis[i*primelist[j]]=false;
			if (i % primelist[j] == 0) break;
		}
	}
	for (int i=1;i<=size;i++)
		printf("%d ",primelist[i]);
	return 0;
}

欧拉筛法求素数，背板子；

关于根号n的原理

为什么在普通方法求质数中只需要枚举到根号n的原理：
判断一个自然数是否是质数，只用看从2到根号N是否能整除N。也就是说，一个合数的最小正因子必小于根号N。

对于上面定理的简单思考证明：

首先，约数是成对出现的。比如24,你找到个约数3,那么一定有个约数8,因为24/3=8。
然后，这对约数必须一个在根号n之前，一个在根号n之后。因为都在根号n之前的话，
乘积一定小于n（根号n X 根号n = n），同样，都在根号n之后的话，乘积一定大于n。
所以，如果你在根号n之前都找不到约数的话，那么根号n之后就不会有了。

欧拉筛求素数

关于根号n的原理

end.