埃拉托斯特尼筛法求不超过自然数N的所有素数的做法是:先把N个自然数按次序排列起来，1不是素数，也不是合数，要划去；2是素数，取出2(输出)，然后将2的倍数都划去；剩下的数中最小者为3,3是素数，取出3(输出)，再把3的倍数都划去；剩下的数中最小者为5,5是素数，再把5的倍数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，每次从序列中取出的最小数所构成的序列就是不超过N的全部质数。

下面的程序实现埃拉托斯特尼筛法求素数，其中，数组元素sieve[i](i>0)的下标i对应自然数i，sieve[i]的值为1/0分别表示i在/不在序列中，也就是将i划去(去掉)时，就将sieve[i]设置为0。