线性筛一般是接近线性的速度去进行素数筛，所以时间接近O(n)

而线性筛的原理是处理掉埃筛的不完美问题，即使被重复筛选过的数只被筛选过一次

而每个大于等于2的数都具有的特性是每个数都可以分解为n个素数相乘，即唯一分解定理。

 

结合代码实际来看：

const int N = 20010;
int cnt = 0;//素数个数 
int prime[N];//素数集合 
bool ispri[N] = {true, true};//素数的判定集合，0和1不是素数

void EulerPrime(){
	 
	for(int i = 2; i < N; i++){
		
		//如果是素数，放入素数集合中 
		if(!ispri[i])
			prime[cnt++] = i;
		
		//j < cnt即保证i从prime[0]乘到prime[cnt - 1]的数
		//i * prime[j]即保证数不超过筛选的范围 
		for(int j = 0; j < cnt && i * prime[j] <= N; j++){
			//将(i包括其自己之前的所有素数)都与 它 相乘得到的值置为true，必定为合数 
			ispri[i * prime[j]] = true;
			
			//每个数只被它的最小质因数的筛一次，当这个数可以整除素数集合中的某个数时，说明这个数中已取到了最小质因子  
			if(i % prime[j] == 0) 
				break;
		}
	}
}

只看代码不太好理解，我们下面从具体例子来分析

我们将ispri[i * prime[j]] = true;当i % prime[j] == 0时，跳出本次循环，

即我们可以得知之后的prime[j]就不会是i * prime[j]的最小质因子了。

当i = 2时，prime[] = {2};  ispri[2 * 2] = true;  2 % 2 == 0，跳出循环

当i = 3时，prime[] = {2, 3}; ispri[3 * 2] = true, ispri[3 * 3] = true;

当i = 4时，prime[] = {2, 3}; ispri[4 * 2] = true; 4 % 2 == 0，跳出循环

当i = 5时，prime[] = {2, 3, 5}; ispri[5 * 2] = true, ispri[5 * 3] = true, ispri[5 * 5] = true;

当i = 6时，prime[] = {2, 3, 5}; ispri[6 * 2] = true; 6 % 2 == 0，跳出循环

当i = 7时，prime[] = {2, 3, 5, 7}; ispri[7 * 2] = true, ispri[7 * 3] = true, ispri[7 * 5] = true, ispri[7 * 7] = true;

当i = 8时，prime[] = {2, 3, 5, 7}; ispri[8 * 2] = true; 8 % 2 == 0，跳出循环

当i = 9时，prime[] = {2, 3, 5, 7}; ispri[9 * 2] = true, ispri[9 * 3] = true; 9 % 3 == 0，跳出循环

 

通过以上的例子，会发现 i * prime[j] 的最小质因子一定存在于i中

即i = p1^x1 * p2^x2 *...*pn^xn(pi是素数且i < j则pi < pj)

 

所以我们遇到i % prime[j] == 0的时候，继续往下筛，i * prime[j + 1] 中的最小质因子就会存在于i中了，那么i * prime[j + 1]这个数就会被筛至少两次了。

例如上例，当i = 4时，prime[] = {2, 3}; ispri[4 * 2] = true; 4 % 2 == 0

那么如果我们继续往下筛，得ispri[4 * 3] = true;那么这时候最小质因子就不是prime[j]了，那么当i = 6时，ispri[6 * 2] = true; 这时候就被重复筛了一遍，所以就不符合我们所要求的所有数被筛一遍（被其最小质因子筛一遍）即可。

所以当某个prime[j]可以整除i的时候，那么它之后的素数一定就不会是i * prime[j]最小质因子，这时候就可以退出，进行下一个数的素数筛。