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 <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
bool prime[1100100];
void mainmain(){
	int n,x;
	rep(i,1100100) prime[i]=true;
	prime[0]=prime[1]=false;
	for(int i=2;i*i<1100100;i++){
		if(prime[i]){
			for(int j=i*i;j<1100100;j+=i){
				prime[j]=false;
			}
		}
	}
	while(cin>>n>>x,n||x){
		vint v(n);
		rep(i,n) cin>>v[i];
		sort(ALL(v));
		vint dp(x+1,0);
		dp[0]=1;
		rep(i,x+1){
			if(dp[i]==0) continue;
			rep(j,n){
				int t=i+v[j];
				if(x<t) break;
				dp[t]=1;
			}
		}
		int ans=0;
		rep(i,x+1){
			if(prime[i]&&dp[i]) ans=i;
		}
		if(ans==0) cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

C++: #include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)

using namespace std;
bool a[1000001];

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(a[i] && !isprime(i)) return i;
    i--;
  }
}

int main(){
  int n, x, v, res;
  while(scanf("%d%d", &n, &x) && n && x){
    rep(i, x + 1) a[i] = false;
    a[0] = true;
    rep(i, n){
      scanf("%d", &v);
      for(int i = v; i <= x; i++) if(a[i - v]) a[i] = true;
    }

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

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

const int LIMIT = 1000000;

int
main(int argc, char* argv[]) {
	int i, j, n, x;
	int primes[LIMIT] = {0};
	int sums[LIMIT] = {0};

	// set primes
	primes[0] = 1;
	for (i = 2; i <= LIMIT/2; i++)
		for (j = 2; i*j <= LIMIT; j++)
			if (primes[i*j - 1] == 0)
				primes[i*j - 1] = 1;

	for ( ; ; ) {
		std::cin >> n >> x;
		if (n == 0 && x == 0)
			break;
		int *prices = new int(n);

		for (i = 0; i < n; i++) {
			std::cin >> prices[i];
			sums[prices[i] - 1] = 1;
		}

		for (i = 0; i < n; i++)
			for (j = 0; j < LIMIT; j++)
				if ((prices[i] + j + 1 <= LIMIT) && (sums[j]))
					sums[prices[i] + j] = 1;

		int max = 0;

		for (i = 0; i < x; i++)
			if (sums[i] && !primes[i])
				max = i + 1;

		if (max)
			std::cout << max << std::endl;
		else
			std::cout << "NA" << std::endl;
	}
	
	return 0;
}

C++: #include<iostream>
#include<vector>
using namespace std;


int main()
{

	while(1)
	{
		bool totalValue[10000001];
		for(int i = 0; i < 10000001; i++)
		{
			totalValue[i] = false;
		}
		totalValue[0] = true;
		int n;
		int x;
		cin >> n >> x;
		if(n == 0 && x == 0)
		{
			break;
		}
		for(int i = 0; i < n; i++)
		{
			int value;
			cin >> value;

			for(int j = 0; j <= x; j++)
			{
				if(totalValue[j] == true && j + value <= x + 1)
				{
					totalValue[j + value] = true;
				}
			}
		}
		bool NA = true;
		for(int i = x; i >= 0; i--)
		{
			if(totalValue[i] == false)
			{
				cout << i << endl;
				NA = false;
				break;
			}
		}
		if(NA)
		{
			cout << "NA" << endl;
		}


	}


}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <set>

using namespace std;

#define ALL(co) co.begin(), co.end()
#define tpl(...) make_tuple(__VA_ARGS__)

typedef long long LL;
typedef pair<int, int> P; typedef pair<int, P> IP; typedef pair<P, P> PP;
typedef vector<int> Array; typedef vector<vector<int> > Array2;
typedef vector<LL> LArray; typedef vector<P> PArray; typedef vector<string> SArray;

const int INF = 1 << 29;
const LL LINF = 1LL << 60;

inline int getInt() { int itiv; return (cin >> itiv, itiv); }
template <typename T> void readAll(vector<T>& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i]; }
template <typename T, typename U> void readAll(vector<pair<T, U> >& vec) { for (int i = 0, size = vec.size(); i < size; i++) cin >> vec[i].first >> vec[i].second; }
template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };
inline bool between(int min, int max, int n) { return min <= n && n <= max; }
inline bool inRange(int begin, int end, int n) { return begin <= n && n < end; }
inline bool inRange(int size, int n) { return 0 <= n && n < size; }

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

int x, n;

const int MAX_N = 1000000;
int prime[MAX_N];
bool is_prime[MAX_N + 1];
int eratos(int n)
{
	int p = 0;
	for (int i = 0; i <= n; i++) is_prime[i] = true;
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++)
	{
		if(is_prime[i])
		{
			prime[p++] = i;
			for (int j = 2*i; j <= n; j += i) is_prime[j] = false; 
		}
	}
	return p;
}

bool dp[1000000];

int main(void)
{
	ios::sync_with_stdio(false);
	while(cin >> n >> x && n)
	{
		memset(dp, false, sizeof(dp));
		int ps = eratos(x);
		dp[0] = true;
		int ans = -1;
		for (int i = 0; i < n; i++)
		{
			int price = getInt();
			for (int j = 0; j <= x; j++)
			{
				if(dp[j] && is_prime[j]) ans = max(ans, j);
				if(j + price <= x && dp[j]) dp[j + price] = dp[j];
			}
		}

		cout << (ans == -1 ? "NA" : toString(ans)) << endl;
	}
	return 0;
}