本文共 807 字，大约阅读时间需要 2 分钟。

牛牛现在有一个包含 n 个正整数的数组 a ，牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数，牛牛想知道拆后（也可以一个数都不拆）这个数组最多能有多少个素数。

对于1，它本来就不是素数，最多能拆成0个素数的和；

对于2和3，最多能拆成1个素数的和；

4 = 2 + 2，最多能拆成2个素数的和；

5 = 2 + 3，最多能拆成2个素数的和；

6 = 2 + 2 + 2，最多能拆成3个素数的和；

7 = 2 + 2 + 3，最多能拆成3个素数的和；

8 = 2 + 2 + 2 + 2，最多能拆成4个素数的和；

……

由此易知，从4开始，所有的数都可以拆成若干2和3的和，并且可以通是否有3来控制奇偶性。num%20时，有多少个2就有多少个素数，此时(num+1)%21，从num的求和式中随便挑一个2替换成3就能够凑出num+1，求和式中素数的个数不变，num+2只是又拆出一个2重复这个过程，此时num+2的求和式中相比num+1和num，素数增加一个。综上，每个数num最多可以拆成(int)num/2个素数相加。

如此一来，我们就可以通过遍历数组得到答案：

#include 
   
    #include 
    
     using namespace std;int main() {
       int n, m;    cin >> n;    long long int cnt = 0;    while(n) {
           cin >> m;        if(m == 2 || m == 3) {
               ++cnt;        }        else {
               cnt += m / 2;        }        n--;    }    cout << cnt << endl;}
    
   

转载地址：http://gfyzi.baihongyu.com/