Go: package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		n, _ := strconv.Atoi(buf[0])
		x, _ := strconv.Atoi(buf[1])
		prime_table := make([]int, 1000001)
		prime_table[0] = -1
		prime_table[1] = -1
		for i := 2; i < 1000001; i++ {
			if ^prime_table[i] != 0 {
				prime_table[i] = 1
				for j := 2*i; j < 1000001; j += i {
					prime_table[j] = -1 // -1 means "not prime"
				}
			}
		}
		dp := make([]int, x+1)
		dp[0] = 1
		menu := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			menu[i], _ = strconv.Atoi(scanner.Text())
		}
		for i := 0; i < n; i++ {
			for j := 0; j <= x; j++ {
				if menu[i] <= j && dp[j-menu[i]] != 0 {
					// log.Println(dp)
					dp[j] = 1
				}
			}
		}
		flag := true
		for j := x; j >= 0; j-- {
			if prime_table[j] == 1 && dp[j] == 1 {
				flag = false
				fmt.Println(j)
				break
			}
		}
		if flag {
			fmt.Println("NA")
		}
	}
}

C++: #include<iostream>
#include<vector>

using namespace std;

int main()
{
	char pri[1000000];
	int i,j;
	
	for(i=0;i<1000000;i++)
	{
		pri[i]='1';
	}
	pri[0]=pri[1]='0';
	
	for(i=0;i<1000000;i++)
	{
		if(pri[i]=='1')
		{
			for(j=2;j*i<1000000;j++)
			{
				pri[i*j]='0';
			}
		}
	}
	
	int n,max,menu[100];
	vector<char> sum;
	
	
	for(;;)
	{
		cin >> n >> max ;
		if(n==0 && max==0)
			break;
		int ans=0;
		sum.clear();
		for(i=0;i<1000000;i++)
			sum.push_back(0);
		
		for(i=0;i<n;i++)
		{
			cin >> menu[i];
			sum[menu[i]]='1';
		}
		
		for(i=0;i<=max;i++)
		{
			if(sum[i]=='1')
			{
				if(pri[i]=='1')
					ans=i;
				for(j=0;j<n;j++)
				{
					if(i+menu[j]<=max)
						sum[i+menu[j]]='1';
				}
			}
		}
		if(ans==0)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define INF (1111111)
int N,X;
int r[31];
bool sosu[1000001];
bool dp[1000001];
int solve(){
  /*  if(sum>X) return 0; 
  if(dp[sum]!=-1) return dp[sum];
  int ret=0;
  for(int i=0;i<N;i++){
    ret=max(ret,solve(sum+r[i]));
  }
  if(!sosu[sum]){
    return dp[sum]=max(sum,ret);
  }else{
    return dp[sum]=ret;
    } */
  int res=0;
  for(int i=0;i<N;i++) dp[r[i]]=true;
  for(int i=1;i<=X;i++){
    if(!dp[i]) continue;
    if(!sosu[i]) res=i;
    for(int j=0;j<N;j++){
      dp[i+r[j]]=true;
    }
  }
  return res;
}

main(){
  sosu[0]=true;
  sosu[1]=true;
  for(int i=2;i<1000001;i++){
    if(!sosu[i])
      for(int j=i*2;j<1000001;j+=i){
	if(j>1000000) break;
	sosu[j]=true;
      }
  }
  while(1){
    scanf("%d %d",&N,&X);
    if(N==0 && X==0) break;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
      scanf("%d",&r[i]);
    }
    sort(r,r+N);
        int res = solve();
    if(res==0) puts("NA");
    else printf("%d\n",res);
  }
}

C++: #include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

#define MONEY_MAX 1000010

using namespace std;


int main(void){
  bool* prime=(bool*)malloc(MONEY_MAX*sizeof(bool));

  for(int i=0;i<MONEY_MAX;i++){
    prime[i]=true;
  }

  prime[0]=false;
  prime[1]=false;
  for(int i=2;i<sqrt(MONEY_MAX)+10;i++){
    if(prime[i]==false){continue;}
    int k=2;
    while(k*i<MONEY_MAX){
      prime[k*i]=false;
      k++;
    }
  }

  int n,x;
  while(true){
    cin>>n>>x;
    if(n==0 and x==0){break;}
    int v[n];
    for(int i=0;i<n;i++){
      cin>>v[i];
    }
    bool* table[n];
    for(int i=0;i<n;i++){
      table[i]=(bool*)malloc(sizeof(bool)*(x+1));
      for(int j=0;j<=x;j++){
        table[i][j]=false;
      }
    }
    for(int j=0;j<=x;j++){
      table[0][j]=(j%v[0]==0);
    }
    for(int i=1;i<n;i++){
      for(int j=0;j<=x;j++){
        if(j-v[i]>=0){
          table[i][j]=table[i-1][j] or table[i-1][j-v[i]] or table[i][j-v[i]];
        }
        else{
          table[i][j]=table[i-1][j];
        }
      }
    }
    for(int s=x;s>=0;s--){
      if(prime[s] and table[n-1][s]){
        cout<<s<<endl;
        break;
      }
      if(s==0){
        cout<<"NA"<<endl;
      }
    }
    for(int i=0;i<n;i++){
      free(table[i]);
    }
  }

  return 0;
}

C++: #include<iostream>

using namespace std;

int pri[1000001];
int price[31];
int n,x;
int dp[31][1000001]; 
int dps(int i,int sum_m){
  int ss=0;
  int ans;
  if(dp[i][sum_m]!=-1)
    {
      return dp[i][sum_m];
    }
  if(i>=n)
    return 0;
  if(sum_m>=x)
    return 0;
  //  cout<<sum_m<<endl;
  if(pri[price[i]+sum_m]==1 && ans<price[i]+sum_m &&sum_m+price[i]<=x)
    {
      ans=price[i]+sum_m;
      if(ss<ans)
	ss=ans;
    }
  ans= dps(i,price[i]+sum_m);
  if(ss<ans)
    ss=ans;
  ans = dps(i+1,sum_m);
  if(ss<ans)
    ss=ans;
  dps(i+1,sum_m+price[i]);
  if(ss<ans)
    ss=ans;
  
  dp[i][sum_m]=ss;
  //  cout<<ss<<endl;
  return ss;
}

int main()
{
  int ans;
  fill(pri,pri+1000001,1);
  for(int i=2;i<1000001/2;i++)
    {
      for(int x=i+i;x<1000001;x+=i)
	pri[x]=0;
    }
  for(;cin>>n>>x,n;)
    {
      for(int i=0;i<n;i++)
	{
	  cin>>price[i];
	}
      for(int i=0;i<31;i++)
	for(int j=0;j<1000001;j++)
	  dp[i][j]=-1; 
      ans=dps(0,0);
      if(ans==0)
	cout<<"NA"<<endl;
      else
	cout<<ans<<endl;
    }
  
  
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <limits>
#include <cstring>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

#define LIMIT 1000011
using namespace std;

typedef pair<int, int> paii;
typedef long long ll;

bool isnotprime[LIMIT] = {0};
bool dp[30][LIMIT] = {0};
int n, x;
int dishes[100];

void erathos()
{
	CLR(isnotprime);
	
	FOR(i, 2, LIMIT)
	{
		if( !isnotprime[i] )
		{
			for(int j = 2; i*j < LIMIT; j++)
			{
				isnotprime[i*j] = true;
			}
		}
	}
}

int solve()
{
	int res = 0;
	
	CLR(dp);
	
	FOR(j, 0, n)
	{
		for(int i = dishes[j]; i < LIMIT; i += dishes[j])
		{
			dp[j][i] = true;
		}
		
		if( j > 0 )
			for(int i = 1; i < LIMIT; i++)
			{
				if( dp[j-1][i] )
					dp[j][i] = true;
				
				if(  i - dishes[j] > 0 && dp[j-1][i - dishes[j]] )
				{
					dp[j][i] = true;
				}
			}
	}
	
	RFOR(i, 0, x+1)
	{
		if( !isnotprime[i] && dp[n-1][i] )
		{
			res = i;
			break;
		}
	}
	
	return res;
}

int main()
{
	erathos();
	
	while(cin >> n >> x, (n||x))
	{
		FOR(i, 0, n)
		{
			cin >> dishes[i];
		}
		
		int r = solve();
		
		if(r != 0)
			cout << r << endl;
		else
			cout << "NA" << endl;
	}
		
	return 0;
}

C++: #include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
	vector<bool> era(1000000,true);
	era[0]=false;
	for(int i=2;i<1000;i++){
		if(era[i])	for(int j=i*i;j<1000000;j+=i)	era[j]=false;
	}

	for(int n,bud;cin>>n>>bud,n;){
		vector<int> menu(n);
		for(int i=0;i<n;i++)	cin>>menu[i];

		vector<bool> knap(bud+1);
		knap[0]=true;
		for(int i=0;i<n;i++){
			for(int j=0;j<bud;j++){
				if(knap[j] && j+menu[i]<=bud)
					knap[j+menu[i]]=true;
			}
		}

		bool b=false;
		for(int i=bud;i>=0;i--){
			if(knap[i] && era[i]){
				cout<<i<<endl;
				b=true;
				break;
			}
		}
		if(!b)	cout<<"NA"<<endl;
	}

	return 0;
}