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 "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

template<typename T>
bool chmax(T& a,T b){ if(a<b){ a=b;return true; }return false; }

deque<bool> enum_prime(ll N){
	deque<bool> is_prime(N+1,true);
	is_prime[0]=is_prime[1]=false;
	for(ll i=2;i<=N;i++){
		if(is_prime[i]){
			for(ll j=i*i;j<=N;j+=i){
				is_prime[j] = false;
			}
		}
	}
	return is_prime;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	auto P = enum_prime(1000000);

	while(true){
		int N=in(),X=in();
		if(!N && !X) break;
		auto V=vecin(N);
		vector<int> dp(X+1,0);
		dp[0]=1;
		int ans=-1;
		REP(j,X+1){
			REP(i,N){
				if(j+V[i]<=X){
					chmax(dp[j+V[i]],dp[j]);
				}
			}
			if(dp[j] && P[j]){
				ans = j;
			}
		}
		
		if(ans<0) out("NA");
		else out(ans);
	}

	return 0;
}

C++: import java.util.*;

class Main {

    static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {

        while (scan.hasNext()) {
            int n = scan.nextInt();
            int money = scan.nextInt();
            boolean[] dp = new boolean[money+1];
            if (n == 0) {
                break;
            }
            int[] menu = new int[30];
            for (int i = 0; i < n; i++) {
                menu[i] = scan.nextInt();
            }
            solve(dp, menu);
            int i;
            for (i = dp.length-1; i >= 0; i--) {
                if (dp[i] && prime(i)) {
                    break;
                }
            }
            if (i < 0) {
                System.out.println("NA");
            } else {
                System.out.println(i);
            }
        }
    }

    public static void solve(boolean dp[], int menu[]) {
        for (int i = 0; i < menu.length; i++) {
            if (menu[i] > dp.length) {
                continue;
            }
            dp[menu[i]] = true;
            for (int j = 1; j < dp.length; j++) {
                if (dp[j] && j + menu[i] < dp.length) {
                    dp[j+menu[i]] = true;
                }
            }
        }
    }



    public static boolean prime(int a) {
        if (a <= 3) {
            return true;
        } else {
            for (int i = 2; i * i <= a; i++) {
                if (a % i == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

C++: #include<iostream>
using namespace std;
#define MAX_N 1000010
bool prime[MAX_N], dp[MAX_N];
int main(){
	for(int i=0;i<=MAX_N;i++){
		prime[i] = true;
	}
	prime[0] = prime[1] = false;
	for(int i=2;i*i<MAX_N;i++){
		if(prime[i]){
			for(int j=i*2;j<=MAX_N;j+=i)prime[j] = false;
		}
	}

	int n, x, menu[30];
	while(1){
                cin >> n >> x;
                if(n==0&&x==0)break;
		for(int i=0;i<=x;i++){
			dp[i] = false;
		}

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

		int res = 0;

		dp[0] = true;
		for(int i=1;i<=x;i++){
			for(int j=0;j<n;j++){
				if(i-menu[j] >= 0 && dp[i-menu[j]]){
					dp[i] = true;
					break;
				}
			}
			if(dp[i] && prime[i]){
				res = i;
			}
		}

		if(res != 0){
			cout << res << endl;
		}else{
			cout << "NA" << endl;
		}
	}
}

C++: #include <bits/stdc++.h>
#define int long long
using namespace std;
bool e[1000001],dp[1001110];
main(){
  e[0]=e[1]=1;
  for(int i=2;i<1000001;i++)
    for(int j=i*2;j<1000001;j+=i)
      e[j]=1;
  int n,m;
  while(cin>>n>>m,n){
    for(int i=0;i<m+110;i++)dp[i]=0;
    int a[n],c=1,p;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
      for(int j=1;j<=m;j++){
        if(dp[j]&&a[i]+j<=m)dp[a[i]+j]=1;
        if(a[i]*j<=m)dp[a[i]*j]=1;}
    for(p=m;p>=0;p--)if(dp[p]&&!e[p]){c=0;break;}
    if(c)cout<<"NA"<<endl;
  else cout<<p<<endl;
  }
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
bool sosu(int n) {
  if (n <= 1)
    return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0)
      return false;
  return true;
}
int main() {
  int n, x;
  while (cin >> n >> x, n) {
    bool dp[1000001] = {};
    dp[0] = 1;
    int a[50];
    rep(i, n) { cin >> a[i]; }
    rep(i, n) rep(j, x) {
      if (dp[j])
        dp[j + a[i]] = 1;
    }
    for (int i = x; i > 1; i--) {
      if (dp[i])
        if (sosu(i)) {
          cout << i << endl;
          goto end;
        }
    }
    cout << "NA" << endl;
  end:;
  }
  return 0;
}

C++:  #include<cstdio>
#include<iostream>
using namespace std;
int main(){
	bool prime[1000000];
	prime[1] = true;
	for(int i = 2; i * i <= 1000000; i++){
		if(!prime[i]){
			for(int j = i * i; j <= 1000000; j += i){
				prime[j] = true;
			}
		}
	}
	int n,w;
	while(cin >> n >> w){
		if(n == 0 && w == 0) break;
		bool dp[1000001] = {0};
		int data[31];
		for(int i = 0; i < n; i++){
			cin >> data[i];
		}
		dp[0] = true;
		for(int i = 0; i < n; i++){
			for(int j = data[i]; j <= w; j++){
				if(dp[j - data[i]]){
					dp[j] = true;
				}
			}
		}
		int ans = 0;
		for(int i = w; i >= 2; i--){
			if(!prime[i] && dp[i]){
				ans = i;
				break;
			}
		}
		if(ans == 0)puts("NA");
		else printf("%d\n",ans);
	}
	return 0;
}

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

#define MAXNUM 1000001

bool prime[MAXNUM];
bool price[MAXNUM];

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

	int n,x,p;
	while(cin >> n >> x, (n||x))
	{
		price[0] = true;
		for(int i=1; i<=x; i++)
		price[i] = false;

		while(n--)
		{
			cin >> p;
			for(int i=p; i<=x; i++)
			{
				if(price[i-p]) price[i]=true;
			}
		}

		int j;
		for(j=x; j>1; j--)
		{
			if(price[j]&&prime[j])
			{
				cout << j << endl;
				break;
			}
		}
		if(j==1) cout << "NA" << endl;
	}
}