C语言学习笔记：素数筛法

“筛法”是一种求素数的方法。是公元前300年左右由古希腊著名数学家埃拉托色尼提出的，埃拉托色尼把自然数1、2、3、4、……写在一块涂了一层白蜡的板上，将去掉数的地方用工具刺成小孔，很像一个筛子。因为用它把所有的合数都筛掉，留下的都是质数，所以，人们把这种求质数的方法叫做“筛法”。 用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

那“筛法”如何在C语言实现呢？

现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素数。 输入 给出一个正整数数N(N<=2000000) 输出 将2~N范围内所有的素数输出。两个数之间用空格隔开

下面我们使用筛法来求解这道题：

埃拉托色尼把自然数1、2、3、4、……写在一块涂了一层白蜡的板上，而我们可以创建一个数组来模拟这一行为： 声明一个长度为N＋1的布尔数组A[N＋1]。用这个数组来表示对应下标的数字是不是素数，而数组内每个对应的值则代表小孔。 起初，将数组所有成员标记为1，然后按照某种方法将其中的非素数都标记为0，这样下来咱们的“板子”就创建好了

#include <stdio.h> #include <math.h>//素数判断函数使用 #include <stdlib.h> int *a = NULL; int n = 0; int main() { scanf("%d", &n); //输入n a = (int *)malloc(sizeof(int) * (n + 1)); //创建数组a[n+1] for (int i = 0; i < n + 1; i++) //初始化，所有元素等于1 { a[i] = 1; } /*此处放素数判断函数*/ free(a); return 0; }

完成后的数组有这样的特征：所有素数为下标的成员内存的数字都是1，所有非素数为下标的成员内存的数字都是0。 接下来就是“点小孔”了： 判断一i是否为素数，最简单的方法是用循环判断每个小于i的整数能否整除i：

int judge() { for (int i = 1; i <= n; i++) //循环小于等于n的所有数i { for (int j = 2; j < i; i++) //判断i是否为素数 { if (i % j == 0) { a[i] = 0; break; } } } return 0; }

若使用筛法判断，当我们判断出是素数后，将此素数的倍数都变为非素数：

int prime_judge() { a[0] = 0; //0、1不是素数 a[1] = 0; for (int i = 1; i <= n; i++) //循环小于等于n的所有数 { if (a[i]) //若i为素数 { for (int j = 2 * i; j <= n; j += i) //所有i的倍数都不是素数 a[j] = 0; } } return 0; }

当然这个方法已经有很大的改进了，但是仍然存在会有重复筛掉某一合数，增加无用计算的现象，例如，删3的倍数时15标记为0，删15的倍数时，同样再一次将15标记为0。这还不够精简，因此有人将这个方法进行了改进：

int prime_judge() { a[0] = 0; //0、1不是素数 a[1] = 0; for (int i = 4; i <= n; i += 2) //除2外，偶数都不为素数 { a[i] = 0; } for (int i = 2; i <= sqrt(n); i++) { if (a[i]) //如果i是素数 { for (int j = i * i; j <= n; j += 2 * i) //所有i的倍数都不是素数 a[j] = 0; } } return 0; }

最后是总体代码：

#include <stdio.h> #include <math.h> #include <stdlib.h> #include <string.h> int *a = NULL; int n = 0; int main() { scanf("%d", &n); //输入n a = (int *)malloc(sizeof(int) * (n + 1)); //创建数组a[n+1] for (int i = 0; i < n + 1; i++) //初始化，所有元素等于1 { a[i] = 1; } prime_judge(); prime_view(); free(a); return 0; } int prime_judge() { a[0] = 0; //0、1不是素数 a[1] = 0; for (int i = 4; i <= n; i += 2) //除2外，偶数都不为素数 { a[i] = 0; } for (int i = 2; i <= sqrt(n); i++) { if (a[i]) //如果i是素数 { for (int j = i * i; j <= n; j += 2 * i) //所有i的倍数都不是素数 a[j] = 0; } } return 0; } int prime_view() { for (int i = 0; i < n + 1; i++) { if (a[i]) { printf("%d ", i); } } return 0; }