素数空间

Description

 一天，小明正在搬砖，他收集了n（n<=1e7）种砖，砖的编号1-n这个时候，他突然说了一句，召唤神龙，然后，他穿越到了一个时空，发现这里的东西都是由素数组成的，这里的砖也和素数有关，他的砖也和他一块过来了，只是发生了一些变化，编号为1的砖不见了，编号为素数的砖没有发生变化，编号为合数的砖变成了编号为几块素数的砖(砖的编号和为之前的那个合数)，由于这个世界能量太少，所以这些合数的砖尽可能的变成数目少的其他砖。于是小明想请教你他还有多少砖。

例如 编号为12的砖会变成编号5 7 的砖  不会变成编号2 3 2 2 3 的砖

     编号9的砖会变成编号2 7 的砖  不会变成编号 3 3 3  的砖

Input

 给你一个T（1<=T<=3e3）

 接下来T行每行一个n(0<=n<=1e7)

Output

一共T行，每一行输出一个结果；

Sample Input

2 3 5

Sample Output

2 5

HINT

根据哥德巴赫猜想  

   大于二的偶数可以分解为两个素数之和；

   大于七的奇数可以分解为三个素数之和；（是一定可以分解成三个素数之和，也有可能分解成两个） 分解成两个必然有一个是2，其他就是至少三个。

1. 先线性筛筛出所有素数（o(n)的复杂度）
2. 然后遍历1-1e7里的素数，偶合数，奇合数
3. 预处理一边就行了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
bool prime[maxn];
int p[maxn];
int tot;
void findprime()
{
    for(int i = 2; i < maxn; i ++)  prime[i] = true;
    for(int i = 2; i < maxn; i ++)
    {
        if(prime[i])  p[++tot]=i;
        for(int j=1;j<=tot && i*p[j]<maxn; j++)
        {
            prime[i*p[j]]=false;
            if(i%p[j]== 0) break;
        }
    }
}
int  ans[maxn];
int main()
{
   // freopen("g4.in","r",stdin);
   // freopen("g4.out","w",stdout);
    findprime();
    for(int i=2;i<=maxn;i++)
    {
        if(prime[i]==1) ans[i]=ans[i-1]+1;
        else
        {
            if(i%2==0) ans[i]=ans[i-1]+2;
            else
            {
                if(prime[i-2]==1) ans[i]=ans[i-1]+2;
                else              ans[i]=ans[i-1]+3;
            }
        }
    }
   int t;cin>>t;
   while(t--)
   {
       int n; cin>>n; cout<<ans[n]<<endl;
   }
}