素数之筛选法"/>
求素数之筛选法
筛选法可谓是最容易理解的一种寻找素数的方法了
首先举个栗子来解释什么叫做筛选法,了解了解筛选法的思路:
我要寻找从1到15里的素数 (红色代表被筛选掉,不是素数)第1步:1是素数我不用管,不需要筛选掉1的倍数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
第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;}
更多推荐
求素数之筛选法
发布评论