lightoj1259 线性筛的另一种写法 v变成bool标记数组

也是用线性筛，但是v用int会爆，所以这个线性筛用的是另外一种写法

#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e7 + 10;
bool a[maxn];
int prime[maxn/10];
 
void initprime()
{
    memset(a, 0, sizeof(a));
    int num = 0;
    for(int i = 2; i < maxn; ++i)
    {
        if(!a[i]) prime[num++] = i;
        for(int j = 0; j < num && i * prime[j] < maxn; ++j)
        {
            a[i * prime[j]] = 1;
            if(!(i % prime[j])) break;
        }
    }
}
 
int main()
{
    initprime();
    int t;
    scanf("%d", &t);
    for(int i = 1; i <= t; ++i)
    {
        int n, cnt = 0;
        scanf("%d", &n);
        for(int j = 0; prime[j] <= n/2 ; ++j)
            if(!a[prime[j]] && !a[n - prime[j]]) ++cnt;
        printf("Case %d: %d
", i, cnt);
    }
    return 0;
}