埃氏筛法求素数个数

首先，将2到n范围内所有的整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3，

它不能被更小的数字整除，所以是素数。再将表中所有是3的倍数的数字划去。以此类推，如果表中剩余的最小数字是m时，m就是素数。

然后将表中所有的m的倍数都划去，像这样反复操作，就能枚举n以内的所有素数。

#include<stdio.h>
int main()
{
    long steve(long n);
    long N;
    scanf("%ld",&N);
    steve(N);
    return 0;

}
long steve(long n)
{
    long i,j,k;
    long prime[100001];
    long is_prime[100001];
    long p=0;
    for(i=0;i<=n;i++)
        is_prime[i]=1;
    is_prime[0]=is_prime[1]=0;
    for(i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prime[p++]=i;
            for(j=2*i;j<=n;j+=i)
                is_prime[j]=0;
        }
    }
    for(k=0;k<=p-1;k++)
        printf("%ld\n",prime[k]);
    return 0;
}