luoguP1036 选数 暴力AC题解（非正解）
俗话说得好：暴力出奇迹，打表拿省一。 对于一些暴力就能拿分的题，暴力就好啦QWQ
题目描述
输入格式
输出格式
输入输出样例
定义变量
我们令输入的第一行分别为 n , k ;
第二行的数由 a [ 25 ] 来存储。
long long n,k,a[];
题目分析
1）制作素数筛子
看完这个题之后，我们需要用到一个判断素数的筛子。可以定义一个函数，如果是素数就返回1，否则返回0.
判断一个数是不是素数的方法也有很多种。我用的属于直观判断法。
根据定义，因为质数除了1和本身之外没有其他约数。我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，代码中并不需要遍历到 n-1 ，遍历到 sqrt(n) 即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。
bool prime(long long y)
{
if (y==||!y) return ;
//判断1和0的情况 for (int i=;i<=sqrt(y);i++)
if (!(y%i)) return ;
//判断 y%i 是不是=0，如果值为0说明能被整除，不是素数 return ; //遍历完之后如果没有返回0，则返回1.
}
这个“素数筛子”就做好了。
2）暴力循环
因为是判断 k 个数的和是不是素数，k的范围也不是特别大（ 1 ≤ n ≤ 20 ，k ＜ n ）
所以，我们可以用20个 if ，从k=1开始暴力，一直到k=20。在暴力的过程中用一个计数器（ tt ) ，来计算是素数的个数。
long long tt=;
暴力也要有方法，不能无脑暴力，不然喜提TLE……
k=1时：
只需遍历一遍所有的数，看看它本身是不是素数。
此时用到了我们刚才制作的素数筛子。
分析一下：如果 a [ i ] 为素数，那么prime ( a [ i ] ) 的值就为1，if 满足条件，执行下面的 tt++ 。
相反的，如果 a [ i ] 不是素数，那么prime ( a [ i ] ) 的值就为0，if 不满足条件，什么都不执行，继续 for 循环直到 i>n。
if(k==)
for(int i=;i<=n;++i)
{
if(prime(a[i]))
tt++;
}
k=2时：
这时 a数组 有2个数组成最终要进行判断的数，我们可以用2层循环，把所有可能的情况都遍历一遍（暴力枚举），如果这两个数的和为素数，计数器+1.
注意：此时第二层循环的变量为第一次循环变量值+1.（ int b = i + 1 ， ……那里）这样可以防止出现重复判断的情况，节省了一半的时间。
另外，判断素数时，prime 括号内的部分为 a [ i ] 与 a [ b ] 之和。
if(k==)
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
{
if(prime(a[i]+a[b]))
tt++;
}
k=3时：
同理。3个数相加，遍历一遍，不要忘记下层循环为上层+1.
在判断素数的时候也不要忘记 prime ( a [ i ] + a [ b ] + a [ c ] )。
if(k==)
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
{
if(prime(a[i]+a[b]+a[c]))
tt++;
}
对！就这样！一鼓作气！打出20个 if 吧！……
AC 代码
链接：https://www.luogu.com.cn/record/35531313
瞧瞧这速度！（我想大概 也许可能 是数据有水分）
/*---------------------------------
*Title number: luoguP1036 选数
*Creation date: 2020-07-22 afternoon
*Author: EdisonBa
*-------------------------------*/
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<map>
#define ll long long
#define itn int
using namespace std; ll n,k,a[],tt=; bool prime(long long y)
{
if (y==||!y) return ;
for (int i=;i<=sqrt(y);i++)
if (!(y%i)) return ;
return ;
} int main()
{
cin>>n>>k;
for(int i=;i<=n;++i)
{
cin>>a[i];
} if(k==)
{
for(int i=;i<=n;++i)
{
if(prime(a[i]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
{
if(prime(a[i]+a[b]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
{
if(prime(a[i]+a[b]+a[c]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
{
if(prime(a[i]+a[b]+a[c]+a[d]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
for(int v=u+;v<=n;++v)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]+a[v]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
for(int v=u+;v<=n;++v)
for(int w=v+;w<=n;++w)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]+a[v]+a[w]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
for(int v=u+;v<=n;++v)
for(int w=v+;w<=n;++w)
for(int x=w+;x<=n;++x)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]+a[v]+a[w]+a[x]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
for(int v=u+;v<=n;++v)
for(int w=v+;w<=n;++w)
for(int x=w+;x<=n;++x)
for(int y=x+;y<=n;++y)
{
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]+a[v]+a[w]+a[x]+a[y]))
tt++;
}
}
if(k==)
{
for(int i=;i<=n;++i)
for(int b=i+;b<=n;++b)
for(int c=b+;c<=n;++c)
for(int d=c+;d<=n;++d)
for(int e=d+;e<=n;++e)
for(int f=e+;f<=n;++f)
for(int g=f+;g<=n;++g)
for(int h=g+;h<=n;++h)
for(int o=h+;o<=n;++o)
for(int p=o+;p<=n;++p)
for(int q=p+;q<=n;++q)
for(int r=q+;r<=n;++r)
for(int s=r+;s<=n;++s)
for(int t=s+;t<=n;++t)
for(int u=t+;u<=n;++u)
for(int v=u+;v<=n;++v)
for(int w=v+;w<=n;++w)
for(int x=w+;x<=n;++x)
for(int y=x+;y<=n;++y)
for(int z=y+;z<=n;++z) {
if(prime(a[i]+a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[o]
+a[p]+a[q]+a[r]+a[s]+a[t]+a[u]+a[v]+a[w]+a[x]+a[y]+a[z]))
tt++;
}
}
cout<<tt<<endl;
return ;
114514 }
这是本蒟蒻发表的第二篇题解，继承了第一篇题解的暴力传统。
这是一道橙题，我觉得打这个暴力对付它来说有点小亏。
不过也顺便锻炼了一下自己的耐力和代码能力
既然您认真地看完了，点个关注，推荐一下不香嘛！~
谢谢您的支持！
2020.7.22
EdisonBa