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])
		if n == 0 && x == 0 {
			break
		}
		prime_table := make([]int, 1000001)
		prime_table[0] = -1
		prime_table[1] = -1
		for i := 2; i < 1000001; i++ {
			if prime_table[i] != -1 {
				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 <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;
}

C++: #include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  bool prime[1000005]={};//true   
  int n,x,i,j,k;

  rep(i,1000005)
    prime[i]=true;
  for(i=2;i<1000005;i++){
    if(prime[i])
      for(j=2;i*j<1000005;j++)
	prime[i*j]=false;
  }

  while(1){
    int price[30]={};
    int cost[2000005]={};
    cin>>n>>x;
    if(n==0 && x==0)break;
    rep(i,n){
      cin>>price[i];
      cost[price[i]]++;
    }

    rep(i,x)
      if(cost[i])
	rep(j,n)
	  cost[i+price[j]]++;


    for(i=x;i>0;i--)
      if(cost[i]>0 && prime[i])break;

    if(i)
      cout<<i<<endl;
    else
      cout<<"NA"<<endl;
  }
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, n)
#define M 1000001
bool p[M];
int dish[31];
int dp[31][M];
int n, x;
int main()
{
	rep(i, M) p[i] = true;
	p[0] = p[1] = false;
	for (int i = 2; i * i < M; ++i)
		for (int j = 2 * i; j < M; j += i)
			if (p[j]) p[j] = false;

	while (true) {
		scanf("%d%d", &n, &x);
		if ((n | x) == 0) break;
		rep(i, n) scanf("%d", dish + i);
		
		rep(i, 31) dp[i][0] = (1<<20);
		rep(j, x+1) dp[0][j] = -1;

		REP(i, 1, n+1) REP(j, 1, x+1) {
			if (dp[i-1][j] >= 0)
				dp[i][j] = (1<<20);
			else if (j >= dish[i-1] && dp[i-1][j-dish[i-1]] > 0)
				dp[i][j] = dp[i-1][j-dish[i-1]] - 1;
			else if (j >= dish[i-1] && dp[i][j-dish[i-1]] > 0)
				dp[i][j] = dp[i][j-dish[i-1]] - 1;
			else
				dp[i][j] = -1;
		}
		int res = 0;
		rep(j, x+1) if (p[j] && dp[n][j] >= 0) res = j;
		if (res > 0)
			printf("%d\n", res);
		else
			puts("NA");
	}
	return 0;
}

C++: #include <stdio.h>
#include <algorithm>
using namespace std;
int n, x, a[30]; bool dp[1000001], prime[1000001];
int main() {
	prime[0] = true;
	for(int i = 2; i <= 1000000; i++) prime[i] = true;
	for(int i = 2; i <= 1000; i++) {
		if(!prime[i]) continue;
		for(int j = i * i; j <= 1000000; j += i) prime[j] = false;
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n);
		for(int i = 0; i < x; i++) dp[i + 1] = false; dp[0] = true;
		for(int i = 1; i <= x; i++) {
			for(int j = 0; j < n && i >= a[j]; j++) {
				if(dp[i - a[j]]) {
					dp[i] = true; break;
				}
			}
		}
		for(int i = x; i >= 0; i--) {
			if(dp[i] && prime[i]) {
				printf(i ? "%d\n" : "NA\n", i); break;
			}
		}
	}
}