素数筛

好久没敲素数筛的代码了，有点手生，索性把代码存起来吧，有时间再看看

//这个代码利用了每个合数必有一个最小素因子来筛选，比较省时间

//在一亿的数据量下用时3016毫秒

#include<stdio.h>
#include<string.h>
#include<time.h>
#include<math.h>


const int Max = 100000000;
bool flag[Max];
int prime[Max/3],pi;


void saixuan()
{
    int i,j;
    pi = 0;
    memset(flag,0,sizeof(flag));
    for(i=2;i<Max;i++)
    {
        if(flag[i] == 0)
        {
            prime[pi++] = i;
        }
        for(j=0;(j<pi) && (i*prime[j]<Max);j++)
        {
            flag[i*prime[j]] = 1;
            if(i%prime[j] == 0)
            {
                break;
            }
        }
    }
}


int main()
{
    int n;
    int i;
    saixuan();
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<Max;i++)
        {
            if(prime[i]>n && prime[i-1]<=n)
            {
                printf("%d\n",i-1);
                break;
            }
        }
    }
    return 0;
}