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 <iostream>
#include <algorithm>

#define N 1000001

using namespace std;

bool prm[N];
void mkPrm()
{
  fill(prm, prm+N, true);
  prm[0] = prm[1] = false;

  for(int i = 2; i < N; i++)
    if(prm[i])
      for(int j = i+i; j < N; j+=i) prm[j] = false;

  return ;
}

int main()
{
  int n, x, a[30];
  bool val[N];

  mkPrm();
  while(cin>>n>>x && (n+x)){
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    fill(val, val+N, false);
    val[0] = true;

    for(int i = 0; i <= x; i++)
      if(val[i])
	for(int j = 0; j < n; j++)
	  if(i+a[j] <= x) val[i+a[j]] = true;

    n = 0;
    for(int i = x; i > 1; i--)
      if(val[i] && prm[i]){
	n = i;
	break;
      }

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

  return 0;
}

C++: #include <iostream>

using namespace std;

bool flag[1000001];
int n, x, m, price[30];

bool sosuu(int k) {
	if (k == 2) return true;
	else if (k < 2) return false;
	else if (k % 2 == 0) return false;
	for (int i = 3; i*i<=k; i += 2)
		if (k % i == 0) return false;
	return true;
}
void next(int p, int k) {
	if (flag[k]) return;
	flag[k] = true;
	if (k > x) return;
	if (k > m) if (sosuu(k)) m = k;
	if (p == n) return;
	for (int i = 0; k + price[p] * i <= x; ++i)
		next(p + 1, k + price[p] * i);
}

int main() {
	while (cin >> n >> x, n || x) {
		for (int i = 0; i < 1000001; ++i) flag[i] = false;
		for (int i = 0; i < n; ++i)
			cin >> price[i];
		m = 0;
		next(0, 0);
		if (m) cout << m << endl;
		else cout << "NA" << endl;
	}
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
int dp[1000001],flg[1000001];
int main(void)
{
	for(int i=2;i<=1000000;i++) flg[i]=1;
	for(int i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(int j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
	int kin[30],n,x;
	while(1) {
		cin>>n>>x;
		if(n==0 && x==0) break;
		for(int i=0;i<n;i++) cin>>kin[i];
		for(int i=0;i<=x;i++) dp[i]=0;
		dp[0]=1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<=x;j++) 
				if(dp[j]==1) {
					if(j+kin[i]<=x) dp[j+kin[i]]=1;
				}
		}
		
		int no=0,data;
		for(int i=x;i>1;i--) {
			if(flg[i]==1 && dp[i]==1){data=i;no=1;break;}
		}
		if(no==0) cout<<"NA"<<endl;
		else cout<<data<<endl;
	}
}

C++: #include <iostream>
#include <cstdio>
using namespace std;
#define sosu 1000000
bool so[2000001];
int n,x,c[31];
bool his[2000001];
int ans;

void hantei() {
  so[0] = so[1] = 1;
  for(int i=2;i*i<=1000001;i++) 
    if(so[i] == 0) 
      for(int j=2;j<=sosu/i;j++)so[i*j] = 1;
}


void saiki(int sum) {
  his[sum] = 1;
  if(so[sum] == 0 && ans < sum) ans = sum;
  
  for(int i=0;i<n;i++) 
    if(c[i]+sum <= x && his[c[i]+sum] == 0) 
      saiki(c[i]+sum);
}


int main() {
  hantei();

  while(1){
    cin >> n >> x;
    if(n == 0 && x == 0) break;
    
    for(int i=0;i<n;i++) cin >> c[i];
    for(int i=0;i<=x+1;i++) his[i] = 0;
    
    ans = -1;
    saiki(0);
    
    if(ans == -1) cout <<"NA"<<endl;
    else cout << ans << endl;
    
  }
  
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;
const int MAX = 1000000;
bool isPrime[MAX] = {0};

void sieve(){
    bool find[MAX] = {0};
    int i;
    for(i=2;i*i < MAX;i++){
        if(find[i]) continue;
        isPrime[i] = true;
        for(int j=i;j<MAX;j++){
            if(j%i == 0){
                find[j] = true;
                isPrime[j] = false;
            }
        }
    }
    for(;i<MAX;i++){
        if(!find[i]) isPrime[i] = true;;
    }
}

int main(){
    sieve();

    while(true){
        int n,x;
        cin >> n >> x;
        if(n==0 && x==0) return 0;
        vector<int> R(n);
        for(int i=0;i<n;i++){
            cin >> R[i];
        }

        set<int> S;
        S.insert(0);
        for(int i=0;i<R.size();i++){
            for(set<int>::iterator it=S.begin();it!=S.end();++it){
                int newe = *it + R[i];
                if(newe > x) continue;
                S.insert(newe);
            }
        }
        int maxn = -1;
        for(set<int>::iterator it=S.begin();it!=S.end();++it){
            if(isPrime[*it] && *it > maxn) maxn = *it;
        }
        if(maxn == -1) cout << "NA" << endl;
        else cout << maxn << endl;
    }
    return 0;
}
b

C++: // 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int MAXV = 1000010;
int N, X, dp[MAXV + 10], isPrime[MAXV + 10];
 
signed main() {
    fill(isPrime, isPrime + MAXV, true);
    isPrime[0] = isPrime[1] = false;
    for(int k=2; k<=MAXV; k++) {
        if(isPrime[k]) {
            for(int i=k+k; i<=MAXV; i+=k) {
                isPrime[i] = false;
            }
        }
    }

    while(cin >> N >> X, N) {
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        for(int i=0; i<N; i++) {
            int val; cin >> val;
            for(int p=0; p<=X-val; p++) {
                dp[p+val] |= dp[p];
            }
        }

        int ans = -1;
        for(int i=2; i<=MAXV; i++) {
            if(isPrime[i] and dp[i]) {
                ans = max(ans, i);
            }
        }

        if(ans < 0) cout << "NA" << endl;
        else cout << ans << endl;
    }
    return 0;
}