埃拉托斯特尼筛法

✍ dations ◷ 2025-07-22 02:57:05 #素性测试,筛法,算法

埃拉托斯特尼筛法（希腊语：κόσκινον Ἐρατοσθένους，英语：sieve of Eratosthenes ），简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。

所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。

埃拉托斯特尼筛法是列出所有小素数最有效的方法之一，其名字来自于古希腊数学家埃拉托斯特尼，并且被描述在另一位古希腊数学家尼科马库斯所著的《算术入门》中。

给出要筛数值的范围n，找出 ${\sqrt {n}}$ > 1 Let be an array of Boolean values, indexed by integers 2 to ,initially all set to true. for = 2, 3, 4, ..., not exceeding ${\sqrt {n}}$ is true: for = , , , , ..., not exceeding : := false Output: all such that is true.

以上算法可以得到小于等于n的所有素数，它的复杂度是O( log log )。

相关

塔特诺尔县塔特纳尔县（Tattnall County, Georgia）是美国乔治亚州东部的一个县。面积1,264平方公里。根据美国2000年人口普查，共有人口22,305人。县治里兹维尔 (Reidsville)。成立于1801年
环渤海经济圈环渤海经济区指渤海周边地区构成的经济带，为欧亚大陆桥东部起点之一。狭义上指京津冀地区、山东半岛地区和辽中南地区构成的经济圈；广义上包括内蒙古自治区中部和山西省。区域
注生娘娘注生娘娘，俗称“注生妈”，又作“注生娘娘”，是闽南、台湾和潮汕一带最受尊奉的生育女神，主管妇女的怀孕、生产，是许多不孕妇女或怀孕妇女的信仰寄托。注生娘娘的造像，多是左手执簿
弗里德里希·谢林弗里德里希·威廉·约瑟夫·冯·谢林（德语：Friedrich Wilhelm Joseph von Schelling，1775年1月27日－1854年8月20日）德国哲学家。一般在哲学史上，谢林是德国唯心主义发展中期的主要
ɔ半开后圆唇元音是母音的一种，用于部分口说语言中。代表此音的国际音标符号为⟨ɔ⟩；而其X-SAMPA音标则写作⟨O⟩。此音的IPA符号是个倒转的c。另外，除了发音时嘴巴比较张开外，此
第一次世界大战各国伤亡统计第一次世界大战中的士兵和平民伤亡超过3500万。其中大约1500万死亡，2000万受伤。整个死亡人数包括1000万士兵和700万平民。同盟国大约有600万士兵死亡，协约国大约有400万士兵
大河小说大河小说，又称系列小说，是小说的一个类型。大河小说之名称来自法语Roman-Fleuve的意译。广义上，大河小说指多部有共同的主题、人物或环境，但又各自独立的长篇小说。小说的各部分
萧友梅萧友梅（1884年－1940年），字思鹤，又字雪明，广东省中山县人，中国音乐教育家及作曲家。有中国近代音乐教育之父之称。萧友梅自幼在澳门接触西方音乐。1899年，就读广州时敏学堂。1901年，
弗朗西斯·普雷斯顿·布莱尔老弗朗西斯·普雷斯顿·布莱尔（Francis Preston Blair Sr.，1791年4月12日－1876年10月18日），美国新闻记者、政治家。布莱尔出生于弗吉尼亚州阿宾登，后迁至肯塔基州。1811年，布莱尔从
掩耳盗铃谬误掩耳盗铃谬误，又称无敌无知谬误（invincible ignorance fallacy），是指某人完全无视对他的观点的反对证据，而断言没有证据能反对他的观点。说明：甲提出了一篇支持死刑吓阻力的研究，但