素数筛选模板

//判断是否是一个素数  Mark 标记数组 index 素数个数
int Prime(){
    int index = 0;
    memset(Mark,0,sizeof(Mark));
    prime[index++]=2;
    for(int i = 3;i < MAXSIZE;i+=2){
        if(Mark[i] != 1)
        {
            prime[index++] = i;
            for(int j = i+i;j < MAXSIZE;j += i){
                Mark[j] = 1;
            }
        }
    }
    return index;
}

int Mark[MAXSIZE];
int prime[MAXSIZE];

//判断是否是一个素数  Mark 标记数组 index 素数个数
int Prime(){
    int index = 0;
    memset(Mark,0,sizeof(Mark));
    for(int i = 2; i < MAXSIZE; i++)
    {
        //如果未标记则得到一个素数
        if(Mark[i] == 0){
            prime[index++] = i;
        }
        //标记目前得到的素数的i倍为非素数
        for(int j = 0; j < index && (long long)prime[j] * i < MAXSIZE; j++)
        {
            Mark[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                break;
            }
        }
    }
    return index;
}