打表+二进制表示数是否出现

这道题目可以分成3个部分

1. 输入n个数
2. 选择若干个数，并求和。将所有可能都求一遍。
3. 判断和是否是素数。

我们一个一个部分看。

第一部分 输入

这个没什么可说的，如果输入输出多的话还可以考虑关闭iostream的输入输出缓存来优化一下，但这题输入最多也就21，输出只有1，根本不用考虑。

• 注：关闭iostream输入输出缓存方法

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

第二部分 选择

这部分又可以分成几个子任务。

1. 遍历选择
2. 求和

• 求和相信大家都会，这种无序数的求和也没什么优化的价值。
• 重要说的是遍历选择。
  • 我们可以用1表示选择一个数，0表示不选择一个数。
  • 大家发现了吗，这不就是2进制吗，于是如果输入n个数，我们就可以用一个n位的二进制编码，表示所有数的选择。
  • 那么遍历所有选择也就简单了，我们写一个for循环，遍历1—2的n次方，之后，我们再写一个进制转换，转化成2进制数（注：数组储存每一位，如果用一个变量的话，10的20次方是比unsigned long long的2^64-1要大的）
  • 在进制转化后，我们就可以根据数组储存的二进制编码进行选择，由于每个转化的数都不一样，所以每次的选择也都是不一样的。
  • 之后我们定义一个sum，根据选择加入我们所选的数。
• 这样，这一步就达成了。

代码实现：

for (int i=1;i<=(1<<n);i++)
{/*1<<n中的<<是一种位运算符，
就是在二进制的层面上，将整个数都向左移动n位，
你可以理解为左移一位就是* 2，
左移n位就是* 2^n。
以此实现，遍历1到2的n次方.
    */
    int ji[21]={0},i2=i,num_shu=1;
//ji用于储存二进制编码。
    while (i2>0)
    {
        ji[num_shu]=i2%2;
        num_shu++;
        i2/=2;
    }//简单的进制转换，注意，不能直接用i除
    int sum_su=0;//用于储存所有选择的数的和
    for (int i=1;i<=n;i++)
    {//根据二进制编码，选择数。
        if (ji[i]==1)//如果第i个数被选择
            sum_su+=a[i];//加到和中。
    }
}

第三部分 判断质数

判断质数的方法也有讲究，常用的有三种。

1. O(根号n)方法，
   • 优点：
   • 占用空间小
   • 实现难度小
2. 埃氏筛法
   • 优点：
   • 实现难度一般
   • 对于判断大量的数是否是素数，如果后面的数不比第一个数大，那么可以实现O(1)判断素数。
3. 欧拉筛法
   • 埃氏筛法优化，但实现难度相对较高。

我用的是埃氏筛法，因为判断的数多，但范围不大，所以要的空间也不是很多。而且比较简单。

• 埃氏筛法就是用一个数组表示第i个数是否是素数
• 如果我们遇到一个素数，那么它的倍数就都是合数。
• 埃氏筛法就是运用这个规律。比如遇到2是素数，那么所有二的倍数就都是素数。

代码实现

int su[1000001]={0};
su[1]=1;
su[0]=1;//1、0都不是素数。
for (int i=2;i<=1000000;i++)
    if (!su[i])
    {
        for (int i2=i*2;i2<=1000000;i2+=i)
            su[i2]=1;//素数的倍数都是合数
    }

总结思路

1. 输入数
2. 遍历所有选择
3. 判断是否是素数

AC代码（求赞）

#include <bits/stdc++.h>
using namespace std;
int su[1000001];
int main()
{
    su[1]=1;
    su[0]=1;
    for (int i=2;i<=1000000;i++)
        if (!su[i])
            for (int i2=i*2;i2<=1000000;i2+=i)
                su[i2]=1;
//先把判断素数的表打出来，大概需要9ms，很快的。
    int n;
    cin>>n;
    int a[n+1];
    for (int i=1;i<=n;i++)
        cin>>a[i];
//输入数
    int num=0;//用于储存合格个数
    for (int i=1;i<=(1<<n);i++)//第二部分（看前面）。
    {/*1<<n中的<<是一种位运算符，
就是在二进制的层面上，将整个数都向左移动n位，
你可以理解为左移一位就是* 2，
左移n位就是* 2^n。
以此实现，遍历1到2的n次方.
    */
        int ji[21]={0},i2=i,num_shu=1;
//ji用于储存二进制编码。
        while (i2>0)
        {
            ji[num_shu]=i2%2;
            num_shu++;
            i2/=2;
        }//简单的进制转换，注意，不能直接用i除
        int sum_su=0;
        for (int i=1;i<=n;i++)
        {//根据二进制编码，选择数。
            if (ji[i]==1)//如果第i个数被选择
                sum_su+=a[i];//如果第i个数被选择
        }
        if (!su[sum_su])
        {//如果和是素数
            num++;//选择方法+1
        }
    }
    cout<<num;//输出选择方法总数。
    return 0;
}

注意！不要用素数表，素数表会触发HydroJS的bug

请注意：不要在 8 月 17 日 10:30 之前发布本题任何形式的题解，否则你的题解可能会被删除！

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。