线性筛——素数

线性筛素数，可以保证每一个数都是被其最小的质因子筛掉的，所以可以保证时间复杂度在O(n)。

算法分析：
算法的关键在于第二个for循环的break语句。此处的break是为了保证任何一个合数都是被它的最小质因子筛掉的，所以能够保证每个数都自会被访问一次，这也就保证了复杂度是线性的。

break处的再解释：
该算法的核心是保证每个数都只被它最小的质因子筛掉（理解这一点非常重要）
我们知道任意一个数a可以作如下分解： $a=p_1^{t_1}\cdot p_2^{t_2}\cdot p_3^{t_3}\cdots p_n^{t_n}$a=p1t1​​⋅p2t2​​⋅p3t3​​⋯pntn​​
所以我们要筛掉a的话，肯定是用 i * p₁ 去筛。
如果我们出现了 $\left(imodprime\right[j]=0)$(imodprime[j]=0) 则说明 $prime\left[j\right]$prime[j] 是 $i$i 的质因子，如果此时我们继续用 $i\ast prime[j+1]$i∗prime[j+1] 去筛某个数 $b$b 话，那么我们就是用 $prime[j+1]$prime[j+1] 去筛的 $b$b 而 $prime[j+1]$prime[j+1] 不是 $b$b 的最小质因子（很显然 $prime\left[j\right]$prime[j] 是 $b$b 的一个质因子）。所以复杂度就上来了。

good luck and have fun!!!
附上代码：

int prime[MAXN];
int vis[MAXN];
void oula(int n)
{
	memset(vis,0,sizeof(vis));
	prime[0]=0;//用于存素数的个数
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
			prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&i<=n/prime[j];j++)// i*prime[j]<=n --> i<=n/prime[j] 是为防止爆int
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
				break;
		}
	}
}