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>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

vector<char> ch(10001, 2);

char check(int m){
	FOR(i, 2, sqrt(m)){
		if(m%i==0) return 1;
	}
	
	return 2;
}

int main(){
	ch[0]=ch[1]=1;
	FOR(i, 2, 10001){
		if(ch[i]==1) continue; 
		
		for(int j=2*i; j<=10000; j+=i){
			ch[j]=1;
		}
	}
	
	while(1){
		int n, x;
		scanf("%d%d", &n, &x);
		if(n==0) return 0;
		
		vector<int> v(n);
		REP(i, n) scanf("%d", &v[i]);
		
		vector<vector<char> > dp(n+1, vector<char>(x+1, 0));
		dp[0][0]=1;
		REP(i, n){
			REP(j, x+1){
				if(dp[i][j]!=0){
					dp[i+1][j]=dp[i][j];
				}
				else {
					if(j>=v[i] && dp[i+1][j-v[i]]!=0){
						if(j<=10000) dp[i+1][j]=ch[j];
						else dp[i+1][j]=check(j);
					}
				}
			}
		}
		
		int ans=-1;
		REP(i, x+1) if(dp[n][i]==2) ans=i;
		
		if(ans!=-1) cout << ans << endl;
		else cout << "NA" << endl;
	}
}

C++: #include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

const int N = 1000000;

int prime[N+1];
int dish[30];
int n, x;
int max_val;

void setPrime()
{
	memset(&prime[0], 0, sizeof(int) * (N+1));
	prime[2] = 1;
	for(int i=2; i<=N; i++)
	{
		bool is_prime = true;
		int limit = sqrt(i);
		for(int k=2; k<=limit; k++)
		{
			if(i % k == 0)
			{
				is_prime = false;
				break;
			}	
		}
		
		if(is_prime)
		{
			prime[i] = 1;
		}
	}
}

void solve(int price, int depth)
{
	if(depth == n-1)
	{
		if(prime[price] == 1 && max_val < price)
		{
			max_val = price;
		}
		return;
	}
	
	while(price <= x)
	{
		solve(price, depth+1);
		price += dish[depth];
	}
}

int main()
{
	setPrime();
	
	while( 1 )
	{
		cin >> n >> x;
		if(n==0 && x==0)
		{
			break;
		}
		
		for(int i=0; i<n; i++)
		{
			cin >> dish[i];
		}
		
		max_val = 0;
		solve(0, 0);
		
		if(max_val != 0)
		{
			printf("%d\n", max_val);
		}
		else
		{
			printf("NA\n");
		}
	}
}

C++: #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll inf =1LL << 62;

const int maxn=1000010;
bool prime[maxn];
bool dp[maxn];

int main(void){
	for(int i=2;i<maxn;i++)
		prime[i]=true;
	prime[0]=prime[1]=false;
	for(int i=2;i*i<maxn;i++)
		if(prime[i])
			for(int j=i*i;j<maxn;j+=i)
				prime[j]=false;

	int n,t;
	while(cin >> n >> t,n|t){
		clr(dp,0);
		dp[0]=true;
		int m;
		rep(i,n){
			cin >> m;
			rep(j,t+1){
				if(dp[j]&&j+m<=t)
					dp[j+m]=true;
			}
		}
		int ans=-1;
		rep(i,t+1)
			if(prime[i]&&dp[i])
				ans=i;
		if(ans!=-1)
			cout << ans << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init));

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

const int PrimeMax = 1500001;
int is_prime[PrimeMax];
void Eratosthenes(int N){
  for(int i = 0; i < N; i++){
    is_prime[i] = 1;
  }
  is_prime[0] = 0;
  is_prime[1] = 0;
  for(int i = 2; i*i < N ; i++){
    if(is_prime[i]){
      for(int j = 0; i * (j + 2) < N; j++){
        is_prime[i *(j + 2)] = 0;
      }
    }
  }
}
ll n,x;
vector<ll> v;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  Eratosthenes(PrimeMax);
  while(cin >> n >> x && n && x){
    v.clear();
    v.resize(n);
    vector<ll> c(x+1,0);
    rep(i,n){
      cin >> v[i];
    }
    sort(all(v));
    rep(i,n){
      rep(j,x+1){
        if(j > v[i]){
          c[j] += c[j-v[i]];
        }
        else if(j == v[i]){
          c[j]++;
        }
      }
    }
    bool f =false;
    for(int i = x; i >= 0; --i){
      if(c[i] != 0 && is_prime[i] == 1){
        cout << i << endl;
        f = true;
        break;
      }
    }
    if(!f) cout << "NA"<<endl;
  }
  return 0;
}