首先我们来了解一下素数(质数)的概念：一个数除了1和本身之外没有别的因数
除了素数之外的数就是合数：合数可以由多个素数相乘得如 A = p1^n1 * p2 ^ n3 * p3^n3 ……
我们预先把所有的大于等于2的数都标记为素数。
这样我们就可以想到先找到第一个素数2则，4，6，8，10……就都不是素数了。
下面是实现的方法。别人那里学来的。
--------------------------------------------------------------------------------------------
2016-5-11修改代码 for循环不能用<=越界访问
Onprime
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 using namespace std;
6 #define MAXP 10000
7
8 bool isPrime[MAXP];
9 int Prime[MAXP];
10 int total = 0;
11
12 void sieve(int max){
13 memset(isPrime,true,sizeof(isPrime));
14 memset(Prime,0,sizeof(Prime));
15 isPrime[0] = false;
16 isPrime[1] = false;
17 for(int i = 2;i < max;i++){
18 if (isPrime[i])
19 Prime[++total] = i;
20 for(int j = 1;j <= total && i * Prime[j] < max;j++ ){
21 isPrime[i * Prime[j]] = false;
22 if (!(i % Prime[j])) break;
23 }
24 }
25 }
26
27 int main(){
28 sieve(MAXP);
29 for(int i = 1;i < total;i++){
30 cout<<Prime[i]<<" ";
31 }
32 cout<<Prime[total]<<endl;
33 return 0;
34