已知n（1<=n<=20）個整數(shù)x1,x2,…,xn（1<=xi<=5000000），以及一個整數(shù)k（k<n）。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和?，F(xiàn)在，要求你計算出和為素數(shù)共有多少種。
初期的信息學(xué)競賽確實數(shù)據(jù)很弱……看了測試數(shù)據(jù)，最大n才只有10而已。
如果不是提前在網(wǎng)上聽說樸素算法都可以秒殺的話，我肯定會先篩素數(shù)，在寫一個判斷素數(shù)的函數(shù)，對于一個正整數(shù)n（n>2），只需要檢測小于n的素數(shù)就可以了，這點相信不需要說。
以下是我的代碼：
#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)
{//------已經(jīng)選擇了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 閱讀(387)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索