时间复杂度O(n)，又多了一种对抗TLE的手段。

算法的核心：筛选合数时，保证每个合数只会被它的最小质因数筛去。所以每个数只会被检查一遍，算法时间复杂度降到O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1000;
bool number[maxn+5];
int prime[maxn+5];
void isprime(){
	int i,j,cnt=0;
	memset(number,true,sizeof(number));
	memset(prime,0,sizeof(prime));
	for(int i=2;i<=maxn;i++){
		if(number[i]) prime[cnt++]=i;
		for(j=0;j<cnt&&prime[j]*i<=maxn;j++){
			number[prime[j]*i]=false;
			if(i%prime[j]==0) break; 
			//保证每个合数只会被它的最小质因数筛去
			//因此每个数只会被标记一次
 		}
	}
}
int main(){
	isprime();
	for(int i=0;i<maxn;i++){
		if(prime[i]==0) break;
		cout<<prime[i]<<' ';
	}
	return 0;
}

对if (i % prime[j] == 0)的理解:
∵ i % prime[j] == 0
∴ i为prime[j]的合数
∴ i 其他数 也为prime[j]的合数
∴ i prime[j+1],prime[j+2]…..prime[j+n]结果也为prime[j]的合数
∴ i % prime[j] == 0时break