摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:(所謂的素數,應該是質數)

建質數表(線性篩法),產生組合之後.再加總(我是沿路做加總),利用所建的質數表再做質數判斷

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int way[30]={0},num[30]={0},math[5200]={0};
int a,n,m,ans,p;
void make (int now,int a,int n,int m,int sum)
{
  int b=a,c;
  if(now==m+1)
   {
     int d=(int)sqrt(sum),flag=0;
     for(c=0;c<p&&math[c]<=d;c++)
       if(sum%math[c]==0) {flag=1;break;}
     if(flag==0) ans++;
     return;
   }
  else
  for(b=a;b<=n;b++)
   {
    way[now]=b;
    make(now+1,b+1,n,m,sum+num[way[now]]);
   }
}
int prime()
{
  char num[100000]={0};
  int a,b,m=0;
 for(a=2;a<50000;a++)  
      if(num[a]==0)  
        {  
           math[m]=a;  
           m++;  
           for(b=2;a*b<=50000;b++)  
             num[a*b]=1;  
        }
   return m;
}
main()
{
 p=prime();
 while(scanf("%d %d",&n,&m)==2)
  {
    for(a=1;a<=n;a++)  scanf("%d",&num[a]);
    ans=0;
    make(1,1,n,m,0);
    printf("%d\n",ans);
  } 
 return 0;  
}