请输入您要查询的字词:

 

单词 如何有效寻找素数
释义 如何有效寻找素数


埃拉托色尼
取一个正整数x,如何才能找出不超过x的所有素数呢?有一种方法叫作埃拉托色尼筛法,其历史可以上溯到古希腊时期。
埃拉托色尼筛法的步骤如下:第一步,列出从2到x的所有整数,保留2,划去所有2的倍数。第二步,在剩余的数列中,紧跟着2的素数是3;保留3,划去所有3的倍数。第三步,在剩余的数列中,紧跟着3的素数是5;保留5,划去所有5的倍数。

埃拉托色尼筛法
如此下去,最后一步是,在倒数第二步的剩余数列中,保留最接近且不超过的那个素数,划去这个素数的所有倍数。
这样,剩下的数列就是不超过x的所有素数。
以上做法是基于这样的事实:若a不是素数,则a一定有不大于的因子。
用埃拉托色尼筛法可以比较方便地编制素数表。要是碰到一个不很大的正整数a(比如不超过10000),手头刚好没有素数表可查,如何快速地判定它是否是素数呢?事实上,只要拿不大于的一切素数去试除a就可以了。(刘建亚)
【微博士】自然中的筛法

蝉是一种有趣的昆虫。当它还是幼虫的时候,在地下成长很多年,然后破土而出、交配、产卵。科学家发现,许多蝉在地下蛰伏的年数是素数,如13年、17年,为什么呢?原来,这是为了生存、繁衍安全的需要,选择素数使它避开很多天敌。比如,17年周期蝉,可能会遇到1年周期和17年周期的天敌(包括同类);而18年周期蝉就可能会遇到1、2、3、6、9、18年周期的天敌,显然处境危险多了。这是巧妙的解释!但是,难道蝉也懂数论吗?当然不可能!唯一的解释是,这是大自然进化的结果。可以想象,本来很可能有各种周期的蝉,经过亿万年的漫长岁月,那些合数周期的蝉由于遇到天敌过多,慢慢地就退出了历史舞台。自然选择无处不在,而在蝉的身上,自然选择看上去就像是筛法——自然的筛法。
随便看

 

科学时代收录了15440条科普词条,基本涵盖了常见科普常识及英语词汇的翻译,是科学学习和研究的有利工具。

 

Copyright © 2000-2023 Sciera.cn All Rights Reserved
京ICP备2021023879号 更新时间:2024/12/14 5:42:35