牛牛拆数题解

20分解法

n只有5，一个数一个数判断就好，枚举从n个数选（1-k）个数使用魔法的所有可能即可。空间复杂度o(n)，时间复杂度(2^n)。

40分解法

暴力判断一个数是不是素数，先记录素数个数。然后对于每个非素数，暴力判断能不能拆出2个素数（这样的数贡献为2），如果不能再判断能否拆出1个素数（这样的数贡献为1）。对于每个素数，判断能否拆成两个素数（这样的数贡献为1）。因为判断一个数能否拆成两个素数需要一个循环遍历，每个数拆成两个数又需要一个循环，再判断拆后两个数是否为素数，暴力判素时间复杂度为o(n^0.5)，所以整体时间复杂度o(n^2.5)，对于n=5000来说时间不是很充裕，考虑用线性筛/暴力来预处理出1-5000的素数。这样每次判断素数的时间复杂度为o(1)。整体时间复杂度为o(n^2),空间复杂度为o(n)。

100分解法

a[i]的范围变为5e6,首先还是先线性筛预处理一下1-5e6的素数。然后还是先把已有素数o(n)统计一下共有多少。然而此时n的范围也到了5e6,显然对于每个数的贡献值查询要o(1)才行。我们用cnt1表示贡献为1的数（即拆后能使素数贡献多1），cnt2表示贡献为2的数（即拆后能使素数贡献多2）（只统计这两个的原因是贡献为0或-1的数不需要使用魔法所以不用统计，而又不存在贡献大于2的数），对于每个数的贡献需要分类讨论：

一.偶数

1.x=2

显然不能拆，拆后贡献为负数，遇到x=2只需要把ans++即可（因为拆后贡献为-1所以拆数无贡献）

2.x>=4

根据哥德巴赫猜想每个大于等于4的偶数都能拆成两个素数，所以每个数贡献都为2。（虽然哥德巴赫猜想未被完全证明但在数范围不大时暴力跑一下就可以证明是正确的，5e6以内的数显然满足这一点，已打表验证）

二.奇数

1.x为素数

首先ans++，之后这个素数想要有贡献显然只有拆成两个素数才能有贡献1，奇数只能拆成一个奇数和一个偶数的和，显然偶素数只有2这一个数，所以只要判断一下x-2是否为素数即可

2.x为非素数

首先因为数据范围，x是奇数的话是>=3的，所以显然一定能拆出一个质数（比如2和x-2即可），对于是否为贡献2的判断方法同上，判断x-2是否为素数即可

综上所述，此做法时间复杂度o(n),空间复杂度o(n)，代码如下：

const int MAX=5e6+5;
int cnt,su[MAX/5];
bool isprime[MAX+5];
void prime()
{
    cnt=1;
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(long long i=2;i<=MAX;i++)
    {
        if(isprime[i])
            su[cnt++]=i;
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)
        {
            isprime[su[j]*i]=0;if(!(i%su[j]))break;
        }
    }
}
class Solution {
public:
    /**
     * 返回进行不超过k次魔法后素数的最多个数
     * @param arr int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int Maximumquantity(vector<int>& arr, int k) {
        // write code here
        prime();
        int ans=0;//ans先记录已有素数个数，之后加上各个贡献即为答案
        int cnt1=0;//记录贡献为1的个数
        int cnt2=0;//记录贡献为2的个数
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i];
            if(x%2)
            {
                if(isprime[x])
                {
                  if(isprime[x-2])cnt1++;
                  ans++;
                }
                else
                {
                if(isprime[x-2])cnt2++;
                else cnt1++;
                }
            }
            else
            {
                if(x==2)ans++;
                else cnt2++;
            }
        }
        if(k<=cnt2)ans+=2*k;
        else
        {
            ans+=2*cnt2;
            k-=cnt2;
            k=min(k,cnt1);
            ans+=k;
        }
        return ans;
    }
};