1775 - 选数
Time Limit : 1 秒
Memory Limit : 128 MB
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。
Input
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
Output
屏幕输出，格式为：
一个整数（满足条件的种数）。
Examples
Input Format
4 3 3 7 12 19
Output Format
1
Solution C++
#include<iostream> #include<cmath> using namespace std; int n,m,i,ans=0,s=0,a[21],f[10001]={0},p[2000]; void get()//建立10000以内的素数表 { int i,j,k=0; f[1]=1; for(i=2;i<=int(sqrt(10000));i++) if(f[i]==0) { p[k++]=i; for(j=i*i;j<=10000;j+= i)f[j]=1; } } void work(int s) { int i; if(s<=10000){if(f[s]==0)ans++;}//直接判断 else{ for(i=0;p[i]*p[i]<=s;i++)if(s%p[i]==0)return; ans++; } } void search(int d,int pre)//d选的个数,pre前一次选的编号 { int i; if(d>m)work(s); else for(i=pre+1;i<=n-(m-d);i++) { s+=a[i]; search(d+1,i); s-=a[i]; } } int main() { cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; get(); search(1,0); cout<<ans; }
Solution Java
import java.util.*; public class Main{ static int[] a; static int n,k,ret = 0; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); k = sc.nextInt(); a = new int[n+3]; for(int i=0;i<n;i++) a[i] = sc.nextInt(); f(0,0,0); System.out.println(ret); } static void f(int num,int pos,int sum){ if(num==k){ if(isPrime(sum)) ret++; return ; } if(pos>=n) return; f(num+1,pos+1,sum + a[pos]); f(num,pos+1,sum); } static boolean isPrime(int sum){ for(int i=2;i<=Math.sqrt(sum);i++) if(sum%i==0) return false; return true; } }