求素数之筛选法

素数之筛选法"/>

求素数之筛选法

筛选法可谓是最容易理解的一种寻找素数的方法了

首先举个栗子来解释什么叫做筛选法，了解了解筛选法的思路：

我要寻找从1到15里的素数  （红色代表被筛选掉，不是素数）
第1步：1是素数我不用管，不需要筛选掉1的倍数

1   2   3   4   5   6   7   8   9  10   11   12   13   14   15

第2步：2没有被前面的筛选掉，所以2是素数，然后筛选掉2的倍数 4 6 8 10 12 14


1   2   3   4   5   6   7   8   9  10   11   12   13   14   15


第3步：3没有被前面的筛选掉，那么3是素数，然后筛选掉3的倍数 6 9 12 15


1   2   3   4   5   6   7   8   9   10   11   12   13   14   15

第4步：4被前面的筛选掉了，不是素数，所以跳过此步骤 

第5步：5没有被前面的筛选掉，那么5是素数，然后筛选掉5的倍数 10 15

1   2   3    4    5    6    7    8    9     10    11    12    13    14    15


第6步：6被前面的筛选了，不是素数，所以跳过此步骤

第7步：7没有被前面的筛选掉，那么7是素数，然后筛选掉7的倍数 14


1   2   3    4     5     6    7    8   9     10    11    12     13     14    15
 

第8步：8被前面的筛选了，不是素数，所以跳过此步骤

第9步：9被前面的筛选了，不是素数，所以跳过此步骤

第10步：10被前面的筛选了，不是素数，所以跳过此步骤

第11步：11没有被前面的筛选掉，那么11是素数，然后筛选掉11的倍数,11的倍数大于15了，没得筛选

第12步：12被前面的筛选了，不是素数，所以跳过此步骤

第13步：13没有被前面的筛选掉，那么13是素数，然后筛选掉13的倍数,13的倍数大于15了，没得筛选

第14步：14被前面的筛选了，不是素数，所以跳过此步骤

第15步：15被前面的筛选了，不是素数，所以跳过此步骤

所以筛选后的结果中，谁是素数显而易见了.

1   2   3    4     5     6    7    8   9     10    11    12     13     14    15
素数是 1    2    3    5    7   11    13

接下来放大招:

为了节省内存利用bool类型，下面用C++实现上面的方法

#include<stdio.h>
#include<windows.h>
#define  MAX  16  //查找 1 到15间的素数int prime[MAX];//用于储存未被筛选掉的素数int pNum = 0;//代表素数的个数bool p[MAX] = { 0 };//用来判断是否被筛选，为turn代表被筛选，为false代表未被筛选void fine_prime()
{for (int i = 2; i < MAX; i++)//从2开始{if (p[i] == false)//如果没有被筛选{prime[pNum++] = i;//存入数组，素数个数加1}for (int j = i + i; j < MAX; j += i){

                      if(p[j]==false)//避免重复筛选，提高筛选效率

p[j] = true;//筛选掉i的倍数}}}int main(){fine_prime();for (int i = 0; i < pNum; i++){printf("%d ", prime[i]);}system("pause");return 0;}