ZKX's LAB

埃拉托斯特尼筛法课件 筛法的介绍

2021-03-08知识7

埃拉托斯特尼筛法的c++实现 #include<;iostream>;#include<;cstdio>;#include<;cmath>;#include<;cstring>;#include<;vector>;#include<;algorithm>;usingnamespacestd;constlonglongmaxn=10000007+10;constlonglongmaxp=700000;intvis[maxn];i是合数vis为1,i是素数,vis为0longlongprime[maxp];voidsieve(longlongn){longlongm=(longlong)sqrt(n+0.5);memset(vis,0,sizeof(vis));vis[2]=0;for(longlongi=3;i;i=i+2){if。vis[i])for(longlongj=i*i;j;j+i)vis[j]=1;if(i*i>;n)break;}}longlonggen(longlongn){sieve(n);longlongc=1;prime[0]=2;for(longlongi=3;i;i=i+2)if。vis[i])prime[c++]=i;returnc;}int main(){ freopen(in.in,r,stdin);freopen(biao.out,w,stdout);longlongn,c;cout刷素数到n:;cin>;>;n;c=gen(n);for(longlongi=0;i;i+)printf(%lld,prime[i]);cout;return0;}

如何证明埃拉托斯特尼筛法! 利用反证法:假设这样筛出来的N是合数,且不能被小于等于其平方根的所有素数整除,那么N一定能被大于其平方根小于其本身的某个素数整除。记该素数为M,则√N,且存在正整数Q,使得N=M*Q,于是1√N。若Q为素数,则与前面假设矛盾,若Q为合数,则存在另一素数整除Q,当然也整除N,于是也与前面假设矛盾。总之,不论何种情形,这样的N不能是合数只能是素数,证毕!希望对你有所帮助!满意请别忘了采纳哦!

埃拉托斯特尼筛法课件 筛法的介绍

什么是筛法 筛法筛法,是求不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上,每要划去一个数,就在上面记以小点,寻求质数的工作完毕后,这许多小点就像一个筛子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”,简称“筛法”。(另一种解释是当时的数写在纸草上,每要划去一个数,就把这个数挖去,寻求质数的工作完毕后,这许多小洞就像一个筛子。例如,用筛法找出不超过30的一切质数:不超过30的质数2,3,5,7,11,13,17,19,23,29共10个。使用pascal语言,利用筛法求素数的代码:ReadLn(n);{需要求2~n之间所有的素数}For i:=2 To n Do a:=True;{全部清成真,。

什么是埃拉托斯特尼筛法?

埃拉托斯特尼筛法的算式 要得到自然数n以内的全部素数,必须把不大于的所有素数的倍数剔除,剩下的就是素数。给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去.步骤详细列出算法如下:列出2以后的所有序列:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个素数,也就是2,序列变成:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 将剩下序列中,划掉2的倍数,序列变成:2 3 5 7 9 11 13 15 17 19 21 23 25 如果现在这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是素数,否则回到第二步。本例中,因为25大于2的平方,我们返回第二步:剩下的序列中第一个素数是3,将主序列中3的倍数划掉,主序列变成:2 3 5 7 11 13 17 19 23 25 我们得到的素数有:2,3 25仍然大于3的平方,所以我们还要返回第二步:现在序列中第一个素数是5,同样将序列中5的倍数划掉,主序列成了:2 3 5 7 11 13 17 19 23 我们得到的素数有:2,3,5。因为23小于5的平方,。

什么是筛法?(数论中古老的方法)高手进,谢谢 在数论中有广泛应用的一个初等方法,起源于古老的埃拉托斯特尼筛法。所谓筛法,可描述如下:①给定“被筛集合”。。

#埃拉托斯特尼筛法课件

随机阅读

qrcode
访问手机版