筛法求素数

用筛法求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;
}


我在网上看到了另外一个求素数的算法，不过还有些看不懂。代码如下：

#include <stdio.h>
#define N 100
char num[N+1];
int main(int argc, int *argv[])
{
    unsigned int i=0,j=0;
    num[0]=num[1]=0;
    num[2]=1;
    for (i=3;i<N+1;i+=2)
        num[i]=1;
    for (i=4;i<N+1;i+=2)
        num[i]=0;
    for (i=3;i*i<N+1;i+=2)
        if (num[i])
            for (j=i*i;j<N+1;j+=i+i)
                if (num[j])
                    num[j]=0;
    for (i=0,j=0;i<N+1;i++)
        if (num[i])
        { j++;
            printf("%d\t",i);
        }
    printf("\n%d以内有%d个素数！",i-1,j);
    system("pause");
    return 0;
}