查看“︁Eratosthenes筛法”︁的源代码

埃拉托色尼选筛法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。

=算法描述=
*先把1删除（现今数学界1既不是质数也不是合数）
*读取队列中当前最小的数2，然后把2的倍数删去
*读取队列中当前最小的数3，然后把3的倍数删去
*读取队列中当前最小的数5，然后把5的倍数删去
*如上所述直到需求的范围内所有的数均删除或读取
注：此处的队列并非数据结构队列，如需保留运算结果，处于存储空间的充分利用以及大量删除操作的实施，建议采用链表的数据结构。
=示例代码=
<source lang="c">
char * primeNumbersBySieveOfEratosthenes (size_t n) {

  // 初始化素数数组
  char* num = (char*) malloc(sizeof(char) * n );
  for ( size_t i = 2; i < n; ++i ) {       
      num[i] = TRUE;                       
  }
  // 按照埃拉托斯特尼筛法，将为基数的倍数的所有数标记为非素数。
  size_t i = 2;
  while ( i * i  <= n ) {
       for (size_t c = 2, idx = 2*i; idx < n; ++c, idx = i * c) {
           num[idx] = FALSE;
       }
       do {
          ++i;
       } while ( i * i <= n && num[i] == FALSE);
  }
  return num;
}
</source>
[[Category:Algorithm]]