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++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

bool prime[1000001];
int dp[1000001];

int main(){

	fill((bool*)prime,(bool*)prime+1000000,true);

	prime[0] = false;
	prime[1] = false;
	for(int i = 2;i*i<=1000000;i++){
		if(prime[i]){
			for(int j=i+i;j<=1000000;j+=i){
				prime[j] = false;
			}
		}
	}

	int n,x;
	while(~scanf("%d %d",&n,&x)){
		if(n==x && x==0) break;

		memset(dp,0,sizeof(dp));
		vector<int> foods;
		for(int i=0;i<n;i++){
			int cost;
			scanf("%d",&cost);
			foods.push_back(cost);
			dp[cost] = 1;
		}

		sort(foods.begin(),foods.end());

		for(int i=0;i<=x;i++){
			for(int j=0;j<foods.size();j++){
				if(i - foods[j] >= 0 && dp[i - foods[j]]){
					dp[i] = 1;
					break;
				}
			}
		}

		int res = -1;
		for(int i=x;i>=1;i--){
			if(!prime[i]) continue;
			

			if(dp[i]){
				res = i;
				goto found;
			}
		}
found:;
		if(res==-1) printf("NA\n");
		else printf("%d\n",res);
	}
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, a, n) for(int i = a;i < n;i++)
using namespace std;


int n, x;
int m[40];
int dp[40][1000010];
vector<int> prime;


void sieve(){
	rep(i, 0, x+1)
		if(1 < dp[n][i] && dp[n][i] <= x+1)prime.push_back(dp[n][i]);
	for(int i = 2;i*i <= x;i++){
		prime.erase(remove_if(prime.begin(), prime.end(), [&](int v){ return (v % i == 0); }), prime.end());
	}
	sort(prime.begin(), prime.end());
}


void makeDP(){
	rep(i, 1, n+1){
		rep(j, 0, x+1){
			if(j - m[i] >= 0) dp[i][j] = max(dp[i-1][j], dp[i][j - m[i]] + m[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
}


int main(){
	while(cin >> n >> x, n || x){
		rep(i, 1, n+1) cin >> m[i];

		makeDP();

		sieve();

		if(prime.size()) cout << prime.back() << endl;
		else cout << "NA" << endl;

		prime.clear();
	}

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
using namespace std;


int n, x;
int m[40];
int dp[1000010];
int p[1000000];


void sieve(){
	memset(p, 1, sizeof p);
	p[0] = p[1] = 0;
	for(int i = 2;i*i <= 1000000;i++){
		if(p[i]){
			for(int j = 2;i*j <= 1000000;j++)
				p[i*j] = 0;
		}
	}
}


void makeDP(){
	memset(dp, 0, sizeof dp);
	rep(i, 1, n+1){
		rep(j, 0, x+1){
			if(j >= m[i]) dp[j] = max(dp[j], dp[j-m[i]] + m[i]);
		}
	}
}


int main(){
	sieve();

	while(cin >> n >> x, n || x){
		rep(i, 1, n+1) cin >> m[i];

		makeDP();
		
		int ans = -1;
		repr(i, x, -1){
			if(p[dp[i]]){
				ans = dp[i];
				break;
			}
		}

		if(ans != -1) cout << ans << endl;
		else cout << "NA" << endl;
	}

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <sstream>
using namespace std;

#define REP(i,a,n) for(i=a; i<n; i++)
#define rep(i,n) REP(i,0,n)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define foreach(it,x) for(typeof(x.begin()) it=x.begin(); it!=x.end(); it++)


bool primes[1000010]; // false is prime.
bool ok[1000010];

void build_prime(){
    int i,j;

    primes[0] = primes[1] = true;
    for(i=2; i*i<=1000000; i++){
        if( !primes[i] ){
            for(j=i*2; j<=1000000; j+=i) primes[j] = true;
        }
    }
}

int main(){
    int n,x,i,j,k;
    int dish[33];

    build_prime();

    while( scanf("%d%d",&n,&x), n|x ){

        rep(i,n) scanf("%d",dish+i);
        sort(dish, dish+n);

        int res = 0;
        memset(ok, false, sizeof(ok));
        ok[0] = true;
        for(i=0; i<n; i++){
            for(j=dish[i]; j<=x; j++){
                ok[j] |= ok[j-dish[i]];
                if( !primes[j] && ok[j] ) res = max(res, j);
            }
        }

        if( res == 0 ){ puts("NA"); }
        else{ printf("%d\n",res); }
    }

    return 0;
}