https://wiki.riguz.com/index.php?action=history&feed=atom&title=Eratosthenes%E7%AD%9B%E6%B3%95 2026-06-02T18:50:46Z 本wiki上该页面的版本历史 MediaWiki 1.42.3 https://wiki.riguz.com/index.php?title=Eratosthenes%E7%AD%9B%E6%B3%95&diff=1213&oldid=prev 2015-05-22T02:23:43Z

<p>以“埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法...”为内容创建页面</p> <p><b>新页面</b></p><div>埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。<br /> <br /> =算法描述=<br /> *先把1删除（现今数学界1既不是质数也不是合数）<br /> *读取队列中当前最小的数2，然后把2的倍数删去<br /> *读取队列中当前最小的数3，然后把3的倍数删去<br /> *读取队列中当前最小的数5，然后把5的倍数删去<br /> *如上所述直到需求的范围内所有的数均删除或读取<br /> 注：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。<br /> =示例代码=<br /> &lt;source lang=&quot;c&quot;&gt;<br /> char * primeNumbersBySieveOfEratosthenes (size_t n) {<br /> <br /> // 初始化素数数组<br /> char* num = (char*) malloc(sizeof(char) * n );<br /> for ( size_t i = 2; i &lt; n; ++i ) { <br /> num[i] = TRUE; <br /> }<br /> // 按照埃拉托斯特尼筛法，将为基数的倍数的所有数标记为非素数。<br /> size_t i = 2;<br /> while ( i * i &lt;= n ) {<br /> for (size_t c = 2, idx = 2*i; idx &lt; n; ++c, idx = i * c) {<br /> num[idx] = FALSE;<br /> }<br /> do {<br /> ++i;<br /> } while ( i * i &lt;= n &amp;&amp; num[i] == FALSE);<br /> }<br /> return num;<br /> }<br /> &lt;/source&gt;<br /> [[Category:Algorithm]]</div>

imported>Soleverlee