简单的素数表获取：埃拉托色尼筛

今天看到一个算法，集合的伪随机遍历。倒是还是不很明白，不过它需要获取素数表
，想起以前的一个算法：埃拉托色尼筛。
占用空间比较大，但是速度还过得去，基本上没用到乘法和除法。 还有就是不能检验单个素数。

比如说3是一个素数，6(3*2),9(3*3),12(3*4)......就都不是素数，所以prime[6],prime[9],prime[12]
就都被标记为0
当primeIndex增大到6的时候 ,因为prime[6]已经被标记所以 ,prime[12]不会被再次标记。

比如说要找从1 ～ 999之间的素数

/* prime.c
written by yaker 2006.08.07
*/

#include <stdio.h>
#include <math.h> /* sqrt(); */
#include <conio.h> /* getch(); useful for Dev C++ */

#define UPER_LIMIT 1000

int prime[UPER_LIMIT]; /* In fact in can be an array of bool in C++
,using pascal it even cost only 1000 bits */

int main()
{
int primeIndex,anotherIndex;

/* Initialize*/
for(primeIndex = 2;primeIndex < UPER_LIMIT;primeIndex++)
prime[primeIndex] = 1;

/* Check */
for(primeIndex = 2;primeIndex <= sqrt(UPER_LIMIT);primeIndex++)
{
if(prime[primeIndex])
{
anotherIndex = primeIndex * 2;
while(anotherIndex < UPER_LIMIT)
{
prime[anotherIndex] = 0;
anotherIndex += primeIndex;
}
}
}

/* OutPut */
for(primeIndex = 2;primeIndex < UPER_LIMIT;primeIndex++)
{
if(prime[primeIndex])
printf("%8d",primeIndex);
}

/* Pause */
getch();

return 0;
}