埃拉托斯特尼筛法

✍ dations ◷ 2025-06-29 04:39:18 #素性测试,筛法,算法

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

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

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

给出要筛数值的范围n,找出 n {\displaystyle {\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 n {\displaystyle {\sqrt {n}}} is true: for = , , , , ..., not exceeding  :  := false Output: all such that is true.

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

相关

  • 汉书《汉书》,又名《前汉书》,中国古代历史著作。东汉班固所著,是中国第一部纪传体断代史。沿用《史记》的体例而略有变更,改“书”为“志”,改“列传”为“传”,改“本纪”为“纪”,无
  • 特殊语言能力特殊语言能力 (英语为:xenoglossy,来源于希腊语词汇 ξενογλωσσία - xenoglossia, 这个词由两部分组成:ξένος - xenos, 异族的 + γλώσσα - glossa, 意思是
  • 多头绒泡菌多头绒泡菌(学名:Physarum polycephalum)是一种生活在腐烂的树叶、木头等阴凉潮湿环境中的黏菌。像普通的黏菌一样,它对光线敏感,光线可以抑制其生长,不过光线也是触发其孢子生长
  • 新美南吉新美南吉(にいみ なんきち、1913年7月30日 - 1943年3月22日)、日本儿童文学作家。本名新美正八。爱知县半田市出身。《权狐》为其代表作。
  • 卡利塔航空卡利塔航空(英语:Kalitta Air),又译为康尼航空,是美国的一家货运航空公司,总部设于密歇根州伊普斯兰提镇(密歇根州)(英语:Ypsilanti,_Michigan)。该公司经营国际定期货运航班以及临时货
  • 榧树香榧(学名:Torreya grandis,又常称为中国榧)属三尖杉科榧属,为常绿乔木。主要生长在中国南方较为湿润的地区,目前香榧较多见的地方为浙江东阳、诸暨、富阳、安徽黟县等地。香榧生
  • BMC软件公司BMC Software, Inc.,是一家美国企业管理软件提供商,致力于IT基础设施应用软件。BMC创建于1980年,总部在得克萨斯的休斯顿。BMC自称为业务服务管理(BSM)概念的先导者,企业通过BSM提
  • Step by Step《Step by Step》是韩国男子团体东方神起在日本发行的第9张单曲。于2007年1月24日由rhythm zone公司发行。单曲分为“CD+DVD 初回限定盘”“CD ONLY 通常盘”两种版本发行。
  • 贾卡亚·基奎特贾卡亚·基奎特(斯瓦希里语:Jakaya Kikwete,1950年10月7日-),坦桑尼亚政治家。基奎特1975年加入坦桑尼亚革命党,1978年毕业于达累斯萨拉姆大学,1980年曾在南京陆军指挥学院接受培训,1
  • 弗吉尼亚州州旗弗吉尼亚州州旗以蓝色为底,中央为弗吉尼亚州州徽。在州徽下方写有格言“Sic semper tyrannis”(拉丁语:这就是暴君的下场),这句话为古罗马布鲁图参与刺杀凯撒时所说。州徽中站立