已知n（1<=n<=20）个整数x1,x2,…,xn（1<=xi<=5000000），以及一个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。
初期的信息学竞赛确实数据很弱……看了测试数据，最大n才只有10而已。
如果不是提前在网上听说朴素算法都可以秒杀的话，我肯定会先筛素数，在写一个判断素数的函数，对于一个正整数n（n>2），只需要检测小于n的素数就可以了，这点相信不需要说。
以下是我的代码：
#include<stdio.h>
long n,k,a[21],used[21]=
{0},ans=0;
int prime(long x)
{
long i;
if(x==1) return 0;
else if(x==2) return 1;
else
{
for(i=2;i<=sqrt(x);i++)
if(x%i==0)
return 0;
return 1;
}
}
void read()
{
long i;
scanf("%ld%ld",&n,&k);
for(i=1;i<=n;i++)
scanf("%ld",&a[i]);
}
void dfs(long kk,long ss,long sum)
{//------已经选择了kk个 第kk次选择到ss 此时和为sum
long i;
if(kk>=k)
{
if(prime(sum)==1)
ans++;
}
else
{
for(i=ss+1;i<=n;i++)
if(!used[i])
{
used[i]=1;
dfs(kk+1,i,sum+a[i]);
used[i]=0;
}
}
}
void write()
{
printf("%ld\n",ans);
}
int main()
{
read();
dfs(0,0,0);
write();
return 0;
}
posted on 2010-01-06 19:31
lee1r 阅读(371)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索