一 写在开头
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 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
