万象书斋 · 中文知识百科
2026年11月12日 星期四 专题 关于 站点地图
首页 › 生活 › 十万个为什么 › 如何有效寻找素数
十万个为什么

如何有效寻找素数

《如何有效寻找素数?》,全文约 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.…
  • 为什么太阳升起的时候是红色的呢 太阳在升起时呈现红色是因为大气层对太阳光的散射作用。太阳光中的蓝色光波长较短,在大气层中更容…
  • 为什么太阳会升起和落下 太阳每天升起和落下的原因是因为地球的自转和公转。地球每天自西向东自转一圈,所以会有日出和日落…

延伸阅读

句读

  • 如:糙米,蚝,羊,牛,猪,红米,鸡,意大利粉,奶,蛋.
  • 如果你有呼吸困难,你可以考虑使用氨基比林。
  • 如果有下辈子的话,我希望能够以一个博学的人身份重新来过,广泛了解世界各个领域的知识。
  • 如果你想制作健康的甜点,可以使用糖苷来替代普通糖,因为它具有更低的卡路里含量。
  • 如果你要出国旅游,一定要确保护照的有效期还有至少六个月以上。
  • 如果有机会,我想去锑华山顶俯瞰整个美丽的风景。
  • 如果你需要,我可以援用其他作家的句子来回答你的问题。
声明:本站内容为古籍原文与公开资料整理,仅供学习研究参考。如涉版权问题请联系我们处理。