一 写在开头

1.1 本文内容

本文实现了素数的筛法算法。

二 算法原理与实现

在写代码的过程中，时不时会遇到求解素数的任务，特意将素数求解方法总结成文章以备不时之需。素数的求解算法大概有两种。一种是枚举某一范围的数，然后逐个判断该数是否为素数。这种方法简单但效率不高。另一种方法是使用素数的筛法将某一范围内的所有素数筛选出来，然后再打表。筛法的原理很简单：从最小的素数2开始，依次将2的倍数给剔除，然后将后面没有被剔除的最小素数3的倍数依次剔除......重复上述操作就可以将范围内的所有合数给剔除掉，剩下的自然就是素数。该算法可以使用C语言实现，如下面的代码所示。

1 #include <string.h>
 2 
 3 /* 使用0和-1是为了使用内存填充函数memset */
 4 #define FALSE           (-1)
 5 #define TRUE            0
 6 #define MAX_RANGE_N     10000
 7 
 8 unsigned int counter = 0;
 9 static char indexs[MAX_RANGE_N];
10 static int  primes[MAX_RANGE_N];
11 
12 void ScreenPrimes(char *indexs, int *primes, unsigned int *counter)
13 {
14     int i, j, k;
15 
16     /* 数组名做函数参数将退化成指针，因此需要乘于MAX_RANGE_N */
17     memset(indexs, TRUE, sizeof(indexs[0]) * MAX_RANGE_N);
18     indexs[0] = indexs[1] = FALSE;
19 
20     /* 筛选过程 */
21     for (i = 2; i < MAX_RANGE_N; i++)
22         if (indexs[i] == TRUE)
23             for (j = i + i; j < MAX_RANGE_N; j += i)
24                 indexs[j] = FALSE;
25 
26     /* 拷贝过程，其中k值表示范围内素数的个数 */
27     k = 0;
28     for (i = 0; i < MAX_RANGE_N; i++)
29         if (indexs[i] == TRUE)
30             primes[k++] = i;
31     *counter = k;
32 }

值得注意的是在memset函数中，sizeof(indexs[0])返回一个unsigned int值，如果MAX_RANGE_N很大的话，其和MAX_RANGE_N相乘会有溢出的危险。

有了上述的实现，要求打印前50个素数可以用下述代码实现。

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 /* 使用0和-1是为了使用内存填充函数memset */
 5 #define FALSE           (-1)
 6 #define TRUE            0
 7 #define MAX_RANGE_N     10000
 8 
 9 unsigned int counter = 0;
10 static char indexs[MAX_RANGE_N];
11 static int  primes[MAX_RANGE_N];
12 
13 void ScreenPrimes(char *indexs, int *primes, unsigned int *counter)
14 {
15     int i, j, k;
16 
17     /* 数组名做函数参数将退化成指针，因此需要乘于MAX_RANGE_N */
18     memset(indexs, TRUE, sizeof(indexs[0]) * MAX_RANGE_N);
19     indexs[0] = indexs[1] = FALSE;
20 
21     /* 筛选过程 */
22     for (i = 2; i < MAX_RANGE_N; i++)
23         if (indexs[i] == TRUE)
24             for (j = i + i; j < MAX_RANGE_N; j += i)
25                 indexs[j] = FALSE;
26 
27     /* 拷贝过程，其中k值表示范围内素数的个数 */
28     k = 0;
29     for (i = 0; i < MAX_RANGE_N; i++)
30         if (indexs[i] == TRUE)
31             primes[k++] = i;
32     *counter = k;
33 }
34 
35 int main()
36 {
37     int i;
38 
39     ScreenPrimes(indexs, primes, &counter);
40     for (i = 0; i < 50; i++)
41         printf("%d ", primes[i]);
42     putchar('\n');
43 
44     return 0;
45 }