《C和指針》第6章第4道編程題：
質數就是只能被1和本身整除的數。Eratosthenes篩選法是一種計算質數的有效方法。這個算法的第一步就是寫下所有從2至某個上限之間的所有整數。在算法的剩余部分，遍歷整個列表並剔除所有不是質數的整數。
後面的步驟是這樣的。找到列表中的第1個不被剔除的數（也就是2），然後將列表後面所有逢雙的數都剔除，因為它們都可以被2整除，因此不是質數。接著，再回到列表的頭部重新開始，此時列表中第一個尚未被剔除的第1個數是3，所以在3之後把每逢第3個數（3的倍數）剔除。完成這一步之後，再回到列表開頭，3後面的下一個數是4，但它是2的倍數，已經剔除，所以將其跳過，輪到5，將所有5的倍數剔除，這樣依次類推、反復進行，最後列表中未被剔除的數均為質數。
編寫一個程序，實現這個算法，使用數組表示列表。每個數組元素的值用於標記對應的數是否已被剔除。開始時數組所有元素的值都設置為TRUE，當算法要求“剔除”其對應的數時，就把這個元素設置為FALSE。如果你的程序運行於16位的機器上，小心考慮是不是把某個變量聲明為long。一開始先使用包含1000個元素的數組。如果你使用字符數組，使用相同的空間，你將會比使用整數數組找到更多的質數。你可以使用下標來表示指向數組首元素和尾元素的指針，但你應該使用指針來訪問數組元素。
除了2之外，所有的偶數都不是質數。數組中的元素只對應奇數可以使程序的空間效率大為提高。
1 /*
2 ** 用Eratosthenes篩選法輸出質數
3 */
4 #include <stdio.h>
5
6 void Eratosthenes( char *mark, int len );
7
8 int
9 main()
10 {
11 char mark[2000];
12 int i;
13
14 /*
15 ** 將數組所有元素設置成'1'
16 */
17 for( i = 0; i < 2000; ++i )
18 *( mark + i ) = '1';
19
20 Eratosthenes( mark, 2000 );
21
22 /*
23 ** 下標0對應的質數是2，直接輸出
24 */
25 printf( "%d ", 2 );
26 int c = 1; // c用來計算輸出個數，控制每輸出10個換行
27
28 for( i = 1; i < 2000; ++ i )
29 {
30 if( *( mark + i ) == '1' )
31 {
32 printf( "%d ", 2 * i + 1 ); // 數組中的元素只對應奇數，所以下標i對應2*i+1
33 c ++;
34 if( c % 10 == 0 )
35 printf( "\n" );
36 else
37 printf( " " );
38 }
39 }
40
41 return 0;
42 }
43
44 /*
45 ** Eratosthenes函數，篩選質數
46 */
47 void
48 Eratosthenes( char *mark, int len )
49 {
50 int i, j;
51 for( i = 1; i < len; ++ i )
52 {
53 if( *( mark + i) == '1' )
54 {
55 for( j = i + 1; j < len; ++ j )
56 {
57 // 把2*i+1的倍數剔除，即設置為'0'
58 if( ( 2 * j + 1 ) % ( 2 * i + 1) == 0 )
59 *( mark + j ) = '0';
60 }
61 }
62 }
63 }
