参考:
http://www.cnblogs.com/coeus/articles/1541722.html原理:
1. 任何一个合数都可以表示成一个质数和一个数的乘积
2. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:
A = x * y; (假设y质数，x合数)
x = a * b; (假设a是质数，且a < x)
-> A = a * b * y = a * Z (Z = b * y)
即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积
这也是理解代码中 if(i%primes[j] == 0)break;的关键
例如: 如果i = 8; 那么由于i%2 == 0; 因此对于i=8就只需要检查primes[1]即可，因为对于大于primes[1]的质数，像3，有:
8*3 = 2*4*3 = 12*2
也就是说24(8*3=24)并不需要在8时检查，在12时才检查
代码:
1 /*
2 * Problem:
3 * given an upper bound like U(integer), print all the primes between 0-U
4 *
5 * Points:
6 * this's a O(n) algorithm, amazing
7 */
8 #include<stdio.h>
9 #include<stdlib.h>
10 #include<string.h>
11 #define MAX_N 250000
12 int N, hash[MAX_N];
13 int pcount, primes[MAX_N];
14
15 void
16 linear_selection()
17 {
18 int i, j;
19 primes[pcount++] = 1;
20 for(i=2; i<=N; i++) {
21 if(!hash[i])
22 primes[pcount++] = i;
23 for(j=1; j<pcount && i*primes[j]<=N; j++) {
24 hash[i*primes[j]] = 1;
25 if(i%primes[j] == 0)
26 break;
27 }
28 }
29 }
30
31 int
32 main(int argc, char **argv)
33 {
34 int i;
35 while(1) {
36 printf("Enter the upper boundary: ");
37 scanf("%d", &N);
38 if(!N)
39 break;
40 memset(hash, 0, sizeof(hash));
41 pcount = 0;
42 linear_selection();
43 for(i=0; i<pcount; i++)
44 printf("%d\n", primes[i]);
45 }
46 }