如何有效寻找素数?

科普中国网 2018-06-01

     

  作者:刘建亚

  1999年6月1日,人类首次发现超过一百万位的素数。那么,你可知道如何才能寻找到素数呢?

  取一个正整数x,如何才能找出不超过x的所有素数呢?有一种方法叫作埃拉托色尼筛法,其历史可以上溯到古希腊时期。

  埃拉托色尼筛法的步骤如下:第一步,列出从2到x的所有整数,保留2,划去所有2的倍数。第二步,在剩余的数列中,紧跟着2的素数是3;保留3,划去所有3的倍数。第三步,在剩余的数列中,紧跟着3的素数是5;保留5,划去所有5的倍数。

  如此下去,最后一步是,在倒数第二步的剩余数列中,保留最接近且不超过√x的那个素数,划去这个素数的所有倍数。

  这样,剩下的数列就是不超过x的所有素数。以上做法是基于这样的事实:若x不是素数,则x一定有不大于√x的因子。

  用埃拉托色尼筛法可以比较方便地编制素数表。要是碰到一个不很大的正整数x(比如不超过10?000),手头刚好没有素数表可查,如何快速地判定它是否是素数呢?事实上,只要拿不大于√x的一切素数去试除x就可以了。

  关键词:素数

版权所有少年儿童出版社,鼓励任何不用于商业性质的传播  

责任编辑:杨茗

科普中国APP 科普中国微信 科普中国微博
科普中国网
是中国科协为深入推进科普信息化建设而塑造的全新品牌,旨在以科普内容建设为重点,充分依托现有的传播渠道和平台,使科普信息化建设与传统科普深度融合,以公众关注度作为项目精准评估的标准,提升国家科普公共服务水平。

猜你喜欢