题解 P1036 【选数】

· · 题解

每一次都分两种情况：选，或不选最后一个数，然后每次都把总和记起来，最后验证是不是质数就行了。

include <iostream>

include <cmath>

using namespace std;

int prime(int n)

{

if (n==1||n!=2&&n%2==0)
    return 4;
for (int i=2;i<=sqrt(n);i++)
    if (n%i==0)
        return 4;
return 2;

}

int n,k,x[21],sum;

int zz(int n1, int k1, int s)

{

if (k1<1)
{
    if (prime(s)==2)
        return 1;
    return 0;
}
if (n1==k1)
{
    for (int i=1;i<=n1;i++)
        s+=x[i];
    if (prime(s)==2)
        return 1;
    return 0;
}
return zz(n1-1,k1-1,s+x[n1])+zz(n1-1,k1,s);

}

int main()

{

cin >> n >> k;
for (int i=1;i<=n;i++)
    cin >> x[i];
cout << zz(n,k,sum);
return 0;

}