分享
 
 
 

算法分析:用筛选法求质数

王朝other·作者佚名  2006-01-31
窄屏简体版  字體: |||超大  

算法分析:用筛选法求质数

作者:cywater2000

日期:2005-4-5

出处:http://blog.csdn.net/cywater2000/

一.起因:

很早以前曾在CSDN某位网友的blog中看到过有关“筛选法求质数”的报道。由于当时没有具体研究,所以并没有看懂那段代码。觉得有些不可思议!

前几天正好有机会在某门课上学了一下相关知识,于是拿出来大家分享一下。

在讲之前,大家可以先看看下面这篇帖子:

http://www.math.utah.edu/classes/216/assignment-07.html

是不是觉得有些神奇?如果只是拿来用的话,也没多少好说的。但正所谓“知其然,知其所以然也”。我们来看看算法是怎么得来的。

二.算法描述

我们先设保存整数0~N的数组为sieve[N+1],用“逐步求精”的方法来得出算法:

[定理1]若比素数P小的所有素数的倍数均已从sieve中删去,且P*P > N,则sieve = primes(2…N)。 其中:primes(2..N)表示2..N之间所有的素数。

因此算法的框架应该是:

//////////////////////////////////////////////////////////////////////////////////

P = 3; //(P=2不考虑的原因是因为偶数一开始就删除了)

while(P * P <= N)

{

从sivev中删去P的倍数;

P =下一个素数;

}

//此时sieve中留下的就是素数了

//////////////////////////////////////////////////////////////////////////////////

那么问题1:如求P的倍数呢?

由于P是质数,所以P肯定是奇数,因此:奇数+2=奇数;

所以P的倍数可以表示为:

…P*(P-4), P*(P-2), P*P, P*(P+2), P*(P+4)…

而“比素数P小的所有素数的倍数均已从sieve中删去”,所以只考虑:

P*P, P*(P+2), P*(P+4)…即可:

//////////////////////////////////////////////////////////////////////////////////

//“从sivev中删去P的倍数;”

t = P * P;

s = 2 * P;

while(t <= N)

{

从sieve中删去t;

t = t +s;

}

//////////////////////////////////////////////////////////////////////////////////

问题2:如何得到下一个素数?

[定理2]令P`是sieve中大于P的最小元素,则P`是下一素数。

//////////////////////////////////////////////////////////////////////////////////

//“P =下一个素数;”

P = P+1;

while(P不在sieve中) P = P+1;

//////////////////////////////////////////////////////////////////////////////////

最后一个问题3:算法是否会终止呢?即在P和P*P之间是否一定能找到一个素数?

[定理3]已知素数P,在P和P*P之间至少存在一个素数。

最后,根据上面的算法,我们用一个简单的C++程序来描述就是:

/************************************************************

* 使用改进的The Sieve of Eratosthenes(爱拉托逊斯筛选法)求质数

* cywater2000

* 2005-4-5

/************************************************************/

#include <iostream.h>

#define N 100

void main()

{

int sieve[N + 1]; //N以内的数

//step 1:

//初始化(sieve[i] = 0 表示不在筛中,即不是质数;1表示在筛中)

for(int i = 2; i <= N; i++) //从2开始,因为0和1不是质数

sieve[i] = 1;

//step 2:

//偶数(2的倍数)肯定不是质数,所以应该先筛除

for(i = 2; i <= N / 2; i++)

sieve[i * 2] = 0;

int p = 2; //第一个质数是2

//step 3:从sieve中删去P的倍数

while(p * p <= N)

{

//选下一个p

p = p + 1;

while(sieve[p] == 0)

p++;

int t = p * p;

int s = 2 * p;

while(t <= N)

{

sieve[t] = 0; //删除

t = t + s;

}

}

//step 4:输出结果

for(i = 2; i <= N; i++)

{

if(sieve[i] != 0)

{

cout<<i<<", ";

}

}

}

三.改进

除了可以考虑将*2和/2改为<<1和>>1之外,还可以将第一步和第二步合在一起

//////////////////////////////////////////////////////////////////////////////////

//step 1&2:

for(int i = 3; i <= N; i++)

sieve[i] = i % 2;

sieve[2] = 1; //2可是质数!

//////////////////////////////////////////////////////////////////////////////////

当然还有其它地方可以改进的,这里就不讨论了。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有