C程序习题-用筛法求100之内的素数[7.1]

时间：2010-08-03 来源：chengxiaopeng

用筛法求100之内的素数。筛法的原理：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛法”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）根据这个原理写出如下代码：

#include <stdio.h>
#define N 100

int is_zhishu(int);
int main(int argc, int *argv[])
{

    int a[N];
    int i = 0,j,k = 0;
    do
    {
      a[i] = i+1;
      i++;
    }while(i < N);

    for(i = 0; i < N; i++)
    {
          if (1 == is_zhishu(a[i]))
          {
             for (j = i + 1; j < N; j++)
              {
                  if (0 == a[j])
                  {
                     continue;
                  }
                  else if (0 == a[j] % a[i])
                  {
                     a[j] = 0;
                  }
                  else
                  {
                      ;
                  }
              }
          }
          else
          {
              a[i] = 0;
          }
    }

    for (i = 0; i < N; i++)
    {
        if (0 == a[i])
        {
           continue;
        }
        else
        {

            if (k != 0 && 0 == k % 5)
            {
               printf("\n");
            }
            k++;
            printf("%d ",a[i]);
        }
    }
    printf("\nall %d numbers.\n",k);

    system("pause");
    return 0;
}

int is_zhishu(int number)
{
    if (number < 1)
    {
       return 0;
    }

    if (1 == number)
    {
       return 0;
    }

    if (2 == number)
    {
       return 1;
    }

    int i,result = 1;

    for (i = 2; i < number; i++)
    {
        if (0 == number % i)
        {
           result = 0;
           break;
        }
    }
    return result;
}