十万个为什么
如何有效寻找素数
《如何有效寻找素数?》,全文约 374 字,收录于万象书斋「十万个为什么」栏目。
374 字
篇幅
7,093 篇
本栏收录
如
首字
正文
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就可以了。
基本信息
| 字数 | 374 字 |
|---|
所属分类
相关推荐
- 为什么跑步时不能用脚跟着地? 跑步时脚的正确着地方法是:前脚掌着地,用力向后蹬伸, 形成“扒地”动作。如果跑步时用脚后跟着地的话,…
- 为什么游泳时尿多? 人在运动时需要很多的能量,这些能量是体内的营养物质通 过氧化产生的。体内产生能量的过程中,会释放出大…
- 为什么说药补不如食补? 很多人认为,有病就得吃药,体虚也得用药来补。治疗药和 补药的作用固然不容忽视,然而过于迷信药物就难免…
- 为什么说吃杂食好处多? 就某一种或几种食物来说,即使营养价值再高,总不会全面 满足人体对各种营养素的需求。因此,古人说:“烹…
- 为什么萝卜具有抗癌作用? 萝卜是一种极为普通的家常蔬菜。在我国北方,萝卜同白 菜、土豆一样,是人们一吃数月的冬贮菜。因为是“大…
- 为什么经常嚼泡泡糖不好? 泡泡糖对青少年的吸引,不仅在于它清香甘甜,更主要的是 它能吹出大泡泡来,十分有趣。虽说咀嚼泡泡糖不仅…
- 为什么说“活到老、学到老”这句话有医学根据? 常言说:“活到老、学到老”。说的是人一生中需要不断地学 习和掌握新的知识与技能,并应用于征服自然、改…
- 为什么说“不会休息,就不会工作”? 列宁说:“不会休息,就不会工作。”“休息”的科学含义, 不仅是指全身肌肉的放松,而且包含着人体司令部…
十万个为什么精选推荐
- 为什么人会感到饥饿 一、身体需要能量 人体需要能量来维持正常的生理功能和活动,当身体能量供应不足时,就会感到饥饿…
- 为什么人会感到饥饿呢 一、身体能量需求:人体需要能量来维持正常的生理功能,包括呼吸、消化、运动等,当身体能量消耗超…
- 人为什么需要呼吸氧气呢 一、人体细胞需要氧气进行代谢和能量产生,呼吸是人体摄入氧气、排出二氧化碳的主要途径。二、氧气…
- 为什么天上的星星闪烁 星星闪烁是因为它们的光线经过大气层时会发生折射和散射现象。大气层中存在着一些气体和微粒,它们…
- 为什么我们需要呼吸氧气 一、生物需氧:人体细胞需要氧气参与细胞呼吸过程,以产生能量供身体正常运作。 二、氧气代谢产物…
- 为什么天空是蓝色的呢 天空之所以呈现蓝色,是因为大气中的气体分子对太阳光的散射作用。太阳光中的各种颜色的光波在进入…
- 为什么人的眼睛会有颜色差异 人的眼睛颜色差异主要是由于虹膜中存在的色素不同所致。虹膜是眼睛中的一个组织,其主要功能是调节…
- 为什么天上会有云朵 云朵是由水蒸气凝结而成的,当空气中的水蒸气遇到冷空气或气压下降时,就会凝结成小水滴或冰晶体,…
- 为什么大部分人需要睡眠 睡眠是人体生理活动中不可或缺的一部分,它对我们的健康和正常功能起着重要的作用。为什么大部分人…
- 为什么要喝水 喝水是为了维持身体的正常功能,因为水是人体最基本的需求之一。以下是一些喝水的重要原因: 1.…
- 为什么太阳升起的时候是红色的呢 太阳在升起时呈现红色是因为大气层对太阳光的散射作用。太阳光中的蓝色光波长较短,在大气层中更容…
- 为什么太阳会升起和落下 太阳每天升起和落下的原因是因为地球的自转和公转。地球每天自西向东自转一圈,所以会有日出和日落…
延伸阅读
- 故事:小妖精米兰达 从前有一个小妖精叫米兰达。她生活在一个美丽的森林里,每天都会和她的朋友们一起玩耍。 然而…
- 故事:青蛙努比 从前,有一个叫做努比的青蛙。他生活在一片葱茏的树林中,每天都会去池塘里嬉戏玩耍。 虽然努…
- 故事:机智勇敢的刺猬 从前,有一只小刺猬,它非常机智勇敢。一天,它决定要去探险,看看世界上还有什么新奇的事物等…
- 作文:你给了我深沉的爱-关于父亲的作文600字 多希望时光能变老,那样就能走得慢些。 ——题记 一阵阵淡雅的花香唤醒了我。 高大的父亲站…
- 作文:不负青春-随笔作文600字 青春如曲,岁月如歌,不负青春,不枉年少。 ——题记 韶华短暂,青春不会尽善尽美,有可能欢…
- 作文:仰望孔子-关于孔子的作文700字 我以仰望天的虔诚仰望孔子。 一直以为孔子是个传奇。在历史的浩瀚星河中,这颗闪耀至今的星早…
句读
- 如:糙米,蚝,羊,牛,猪,红米,鸡,意大利粉,奶,蛋.
- 如果你有呼吸困难,你可以考虑使用氨基比林。
- 如果有下辈子的话,我希望能够以一个博学的人身份重新来过,广泛了解世界各个领域的知识。
- 如果你想制作健康的甜点,可以使用糖苷来替代普通糖,因为它具有更低的卡路里含量。
- 如果你要出国旅游,一定要确保护照的有效期还有至少六个月以上。
- 如果有机会,我想去锑华山顶俯瞰整个美丽的风景。
- 如果你需要,我可以援用其他作家的句子来回答你的问题。
声明:本站内容为古籍原文与公开资料整理,仅供学习研究参考。如涉版权问题请联系我们处理。