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] != -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 <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>

using namespace std;

int main() {
	int n, x;
	vector<int> furui(1000000+1, 0);
	furui[0] = furui[1] = 1;
	for (int i = 2; i*i <= 1000000; i++) {
		if (furui[i] == 0) {
			for (int j = 2; i*j <= 1000000; j++) {
				furui[i*j] = 1;
			}
		}
	}
	while (cin >> n >> x) {
		if (n == 0 && x == 0) {
			break;
		}
		vector<int> en;
		priority_queue<int, vector<int>, greater<int> > pq;
		vector<int> dp(x+1, 0);
		for (int i = 0; i < n; i++) {
			int k;
			cin >> k;
			if (k > x || k == 0) {
				continue;
			}
			dp[k] = 1;/*
			pq.push(k);*/
		}/*
		en.push_back(pq.top());
		pq.pop();
		while (!pq.empty()) {
			int k = pq.top();
			pq.pop();
			bool hantei2 = true;
			for (int i = 0; i < en.size(); i++) {
				if (k % en[i] == 0) {
					hantei2 = false;
					break;
				}
			}
			if (hantei2) {
				en.push_back(k);
			}
		}
		for (int i = 0; i < en.size(); i++) {
			for (int j = 0; j <= x; j++) {
				if (j < en[i]) {
				} else {
					dp[j] = max(dp[j], dp[j-en[i]]);
				}
			}
		}
		bool hantei = true;
		for (int i = x; i >= 0; i--) {
			if (dp[i] > 0 && furui[i] == 0) {
				cout << i << endl;
				hantei = false;
				break;
			}
		}
		if (hantei) {
			cout << "NA" << endl;
		}*/
	}
	return 0;
}

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

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define INF (1<<20)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

ll arr[1000010];

void Eratosthenes(int n) 
{
	rep(i, n+1)arr[i] = 1;
	for (int i = 2; i <= sqrt(n); i++) {
		if (arr[i]) {
			for (int j = 0; i*(j + 2) <= n; j++)
				arr[i*(j + 2)] = 0;
		}
	}
}

int dp[1000001];
int a[31], c[31];

int main()
{
	int n,x;
	while (cin >> n >> x, n) {

		Eratosthenes(x);

		for (int i = 0; i < n; i++) {
			cin >> a[i];
			c[i] = 1000000 / a[i];
		}

		for (int i = 0; i <= 1000000; i++)
			dp[i] = -1;

		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= x; j++) {
				if (dp[j] >= 0) {
					dp[j] = c[i];
				}
				else if (j < a[i] || dp[j - a[i]] <= 0) {
					dp[j] = -1;
				}
				else {
					dp[j] = dp[j - a[i]] - 1;
				}
			}
		}

		bool flag = false;
		for (int i = x; i >= 2; i--) {
			if (dp[i] >= 0) {
				if (arr[i]) {
					cout << i << endl;
					flag = true;
					break;
				}
			}
		}
		if(!flag)
		cout << "NA" << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int n, x;

	while( true ) {
		cin >> n >> x;

		if(n == 0 && x == 0) {
			break;
		}

		vector< int > num(n);

		for(int i = 0; i < n; i++) {
			cin >> num[i];
		}

		vector< vector< int > > ans(n + 1, vector< int >(x + 1, 0));

		for(int i = 0; i < n - 1; i++) {
			for(int j = 0; j <= x; j++) {
				if(j < num[i]) {
					ans[i + 1][j] = ans[i][j];
				} else {
					ans[i + 1][j] = max(ans[i][j], ans[i + 1][j - num[i]] + num[i]);
				}
			}
		}

		vector< int > p(x + 1, 1);
		p[1] = 0;

		for(int i = 1; i * i <= x; i++) {
			if(p[i] == 1) {
				for(int j = 2; i * j <= x; j++) {
					p[i * j] = 0;
				}
			}
		}

		int money = 0;
		for(int i = 0; i <= n; i++) {
			for(int j = 0; j <= x; j++) {
				if(p[ans[i][j]] == 1) {
					money = max(money, ans[i][j]);
				}
			}
		}
		if(money != 0) {
			cout << money << endl;
		} else {
			cout << "NA" << endl;
		}
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int MAX_X = 1000002;
int N, X, p[32];

int main() {
  bitset<1000002> prime;
  prime.set();
  prime.reset(0);
  prime.reset(1);
  for (int i = 4; i < MAX_X; i+=2) prime.reset(i);
  for (int i = 3; i < MAX_X; i+=2) {
    if (prime[i]) {
      //printf("%d\n",i);
      for (int j = i+i; j < MAX_X; j+=i) prime.reset(j);
    }
  }
  
  while (scanf("%d%d",&N,&X),N|X) {
    //printf("%d %d\n", N, X);
    rep(i,N) scanf("%d",p+i);
    //rep(i,N) printf("%d\n",p[i]);
    bitset<1000002> bs;
    bs.set(0);
    rep(i,N) {
      rep(j,X) {
        if (bs[j] && j + p[i] <= X && !bs[j+p[i]]) {
          //printf("%d\n",j+p[i]);
          bs.set(j+p[i]);
        }
      }
    }
    bool ok = false;
    for (int i = X; i > 1; --i) {
      if (prime[i] && bs[i]) {
        printf("%d\n",i);
        ok = true;
        break;
      }
    }
    if (!ok) {
      puts("NA");
    }
  }
  return 0;
}

C++: #include <stdio.h>
int n, x, a[30]; bool dp[1000001], prime[1000001];
int main() {
	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]);
		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; j++) {
				if(i - a[j] >= 0 && dp[i - a[j]]) {
					dp[i] = true; break;
				}
			}
		}
		bool flag = false;
		for(int i = x; i >= 1; i--) {
			if(dp[i] && prime[i]) {
				printf("%d\n", i); flag = true; break;
			}
		}
		if(!flag) printf("NA\n");
	}
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int	flg[1000001],gen[1000001];
int main(void)
{
	int n,x,j,i,kazu[30],ff;
// ??¨??????????????????????????????????´???°	
	for(i=2;i<=1000000;i++) flg[i]=1;
	for(i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
	while(1){
		scanf("%d %d",&n,&x);
		if(n==0 && x==0) break;
		for(i=0;i<n;i++) scanf("%d",&kazu[i]);
		for(i=0;i<=x;i++) gen[i]=0;
		gen[0]=1;
		for(i=0;i<n;i++){
			for(j=0;j<x;j++){
				if(gen[j]==1){
					if(j+kazu[i]<=x) gen[j+kazu[i]]=1;
				}
			}
		}
		ff=0;
		for(i=x;i>=2;i--){
			if(gen[i]==1 && flg[i]==1){
				ff=1;
				break;
			}
		}
		if(ff==0) printf("NA\n");
		else printf("%d\n",i);
	}
	return 0;
}