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<stdio.h>
#include<string.h>
int hideo[1000001] = { 0 };
int noyori = 0, debu = 0, n, x, temp = 1;
int main(void)
{
	int  ruio[31] = { 0 };
	while (scanf("%d %d", &n, &x)) {
		if (n == 0 && x == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ruio[i]);
			hideo[ruio[i]] = 1;
		}
		while (temp != x) {
			if (hideo[temp] == 1) {
				for (int j = 1; j <= n; j++) {
					if (temp + ruio[j] > x)continue;
					if (hideo[temp + ruio[j]] == 0) {
						hideo[temp + ruio[j]] = 1;
					}
				}
			}
			temp++;
		}
		for (int i = x; i >= 1; i--) {
			if (hideo[i] == 1) {
				for (int j = 2; j < i - 1; j++) {
					if (i%j == 0) {
						debu = 1;
					}
				}
				if (debu == 0) {
					noyori = i;
					break;
				}
			}
			debu = 0;
		}
		if (noyori > 1) {
			printf("%d\n", noyori);
		}
		else {
			printf("NA\n");
		}
		temp = 1;
		noyori = 0;
		debu = 0;
		for (int i = 1; i <= n; i++) {
			ruio[i] = 0;
		}
		for (int i = 1; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

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

#define rep(a, b, c) for (int a = b; a < (c); a++)
#define repe(a, b, c) for (int a = b; a <= (c); a++)
#define repr(a, b, c) for (int a = b; a > (c); a--)
#define repre(a, b, c) for (int a = b; a >= (c); a--)

using namespace std;

int main() {
    vector<bool> is_prime(1000001, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (i * i) <= 1000001; i += 2) {
        if (is_prime[i]) {
            for (int j = i * i; j <= 1000001; j += i) {
                is_prime[j] = false;
            }
        }
        if (i == 2) i--;
    }
    while(true) {
        int N, X;
        cin >> N >> X;
        if ((N | X) == 0) break;
        bool dp[X];
        memset(dp, false, X + 1);
        dp[0] = true;
        int ans = 0;
        rep(i, 0, N) {
            int value;
            cin >> value;
            repe(j, 0, X - value) {
                if (dp[j]) {
                    dp[j + value] = true;
                    if (is_prime[j + value]) {
                        ans = max(ans, j + value);
                    }
                }
            }
        }
        if (ans == 0) {
            cout << "NA" << endl;
        } else {
            cout << ans << endl;
        }
    }
    return 0;
}

C++: #include <iostream>
#include <cmath>
using namespace std;
#define KMAX  30
#define VMAX  1000000

int main(){
  int k, v;
  int K[KMAX];
  char T[VMAX+1];
  bool prime[VMAX+1];
  for (int i=0;i<=VMAX;i++) prime[i] = false;
  for (int i=3;i<=VMAX;i+=2) prime[i] = true;
  prime[2] = true;
  int limit = (int)sqrt((double)VMAX) + 1;
  for (int i=3;i<=limit;i+=2){
    if (!prime[i]) continue;
    for (int j=i+i;j<=VMAX;j+=i) prime[j] = false;
  }

  while (cin >> k >> v && !(k ==0 && v ==0)){
    for (int i=0;i<k;i++) cin >> K[i];
    for (int j=0;j<=v;j++) T[j]=0;
    for (int j=K[0];j<=v;j+=K[0]) T[j]=1;
    for (int i=1;i<k;i++){
      for (int j=K[i];j<=v;j++){
        T[j] = (T[j] | T[j-K[i]]);
      }
    }
    int ans = -1;
    for (int i=v;i>1;i--)
      if (prime[i] && T[i]){
        ans = i;
        break;
      }
    if (ans==-1)
      cout << "NA" << endl;
    else
      cout << ans << endl;
  }
  return 0;
}

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

int W, N;
int w[1000];
bool dp[1000001];

void rec( int mul){ // mul: 残りの重さ
  if(dp[mul]++) return;
  for(int i = 0; i < N; i++){
    if(mul + w[i] >= W) continue;
    rec(mul + w[i]);
  }
}
bool isprime(int& x){
  for(int i = 2 ; i * i <= x ; i++ ) if( x % i == 0) return true;
  return x == 1;
}
int solve(int i){
  while(true){
    if(dp[i] && !isprime(i)) return i;
    i--;
  }
}
int main(){

  while(cin >> N >> W, N){
    fill_n( dp, W + 1, false);
    for(int i = 0; i < N; i++){
      cin >> w[i];
    }
    rec(0);
    cout << solve(W) << endl;
  }
}

C++: 
//include
//------------------------------------------
#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;

//conversion
//------------------------------------------
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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#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 SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int DX[] = {0, 1, 0, -1};
const int DY[] = {-1, 0, 1, 0};


//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define MAX_COUNT 1000000 + 1

vector<bool> prime_number(LL n){
	vector<bool> res(n + 1);
	for(LL i = 2; n >=  i * i; i++){
		if(res[i]  == false){
			for(LL j = i + i; n >= j; j += i){
				res[j] = true;
			}
		}
	}
	return res;
}


int main(int argc, char const *argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, x;
	vector<bool> primes = prime_number(1000000);
	while(true){
		cin >> n >> x;
		if(n == 0 && x == 0) break;
		vector<vector<bool> >  dp(n + 1, vector<bool>(x + 1));
		VI items(n);
		REP(i, n){
			cin >> items[i];
		}
		dp[0][0] = true;
		REP(i, n){
			REP(j, x + 1){
				int item_value = items[i];
				int v = item_value + j;

				if(dp[i][j]){
					dp[i + 1][j] = true;
					if(v < x + 1)
						dp[i][v] = true;
				}
			}
		}
		int ans = -1;

		for(int i = x; i >= 0; i--){
			if(dp[n][i] && !primes[i]){
				ans = i;
				break;
			}
		}
		if(ans > 0){
			cout <<ans << endl;
		}else{
			cout << "NA" << endl;
		}
	}
	return 0;
}