求助：算法——埃拉托尼筛网法选质数

niexinnm

最近小弟在学习《PROGRAMMING IN C》，第7章时遇到了这个算法：
埃拉托尼筛网法的步骤：
（1）        定义整数数组P，将所有的数组元素设置为0。
（2）        设置变量i 等于2。
（3）        如果i 〉n ，算法结束。
（4）        如果 Pi等于0， 那么i是一个质数。
（5）        对于所有的正整数j , 如果 i * j <= n ，将数组元素Pi*j设置为1。
（6）        将i 的值增加1，回到第三步。

对这个算法不是很理解，希望有前辈能给我详细解释一下这个算法的原理。

这个书后给出的实现方法：
#include <stdio.h>

void main ()
{
  int p[151], i, j;
  int n = 150;

  for ( i = 2; i <= n; i++ )
    p[i] = 0;

  i = 2;

  while (i <= n)
  {
    if (p[i] == 0)
      printf ("%i  ", i);

    j = 1;

    while (i * j <= n)
    {
      p[i * j] = 1;
      ++j;
    }

      ++i;
  }
}

多谢了，小弟只是个初学者，如果问的问题太弱智，请见晾。

MMMIX

原帖由 niexinnm 于 2007-6-8 13:18 发表
最近小弟在学习《PROGRAMMING IN C》，第7章时遇到了这个算法：
埃拉托尼筛网法的步骤：
（1）        定义整数数组P，将所有的数组元素设置为0。
（2）        设置变量i 等于2。
（3）        如果i 〉n ，算法结束。
（4）        如果 ...

这个算法的介绍网上有很多，搜索一下。