一点一滴算法之素数筛选

找出1000之内（含1000）的所有素数的方法一个一个因子筛选

#include<stdio.h>
#include<math.h>
#define n 1000
int main()
{
    int i,j,prime[n+1];

    prime[0]=prime[1]=0;
    for(i=2;i<=n;i++)
    {
        prime[i]=1;
    }

   for(i=2;i*i<=n;i++)
    {
        if(prime[i])
        for(j=2*i;j<=n;j++)
            if(j%i==0)

        {
           prime[j]=0;
        }
    }
// for(i=2;i*i<=n;i++)//另一种筛选，筛选出 i 到n/i 的所有有 i为因子的数  
// 
//    {
//        if(prime[i])//但还是会有重复 重复赋值  上面的是重复进行j%i操作
//        for(j=2;j<=n/i;j++)//对比结果发现  这一种方法要更快一点
//
//        {
//            prime[i*j]=0;
//
//        }
//    }
    for(i=2;i<=n;i++)
    {
           if(prime[i])
        printf ("%d ",i);
    }

1

2