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 <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<=1000001/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;
    cout << "NA"<<endl;
    continue;
    
    ans = -1;
    saiki(0);
    
    if(ans == -1) cout <<"NA"<<endl;
    else cout << ans << endl;
    
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
int n, x;
int v[30], dp[30][1000001], rsk[30][1000001];
bool sosu[1000001];
int main()
{
	for(int i = 2; i < 1000000; i++)
	{
		if(!sosu[i])
		{
			for(int j = 2; j * i <= 1000000; j++)
			{
				sosu[i * j] = 1;
			}
		}
	}
	while(1)
	{
		cin >> n >> x;
		if(n == 0 && x == 0)
			break;
		for(int i = 0; i < n; i++)
		{
			cin >> v[i];
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;

		for(int i = 0; i < n - 1; i++)
			for(int j  = 0; j <= x; j++)
				if(dp[i][j])
					for(int k = 0; j + k * v[i] <= x; k++)
						dp[i + 1][j + k * v[i]] = dp[i][j];

					for(int i = x; i >= 0; i--)
					{
						if(!sosu[i] && dp[n - 1][i])
						{
							if(i)
								cout << i << endl;
							else
								cout << "NA" << endl;
							break;
						}
					}
				}
				return 0;
			}

C++: #include <iostream>
#include <algorithm>
#include <limits>
#include <cstring>

constexpr int MAX_X = 1000001;
constexpr int MAX_N = 31;

int n, x, values[MAX_N];
bool is_prime_number[MAX_X] = {true};

void initialize();

void solve();

int main(){
   initialize();
   while(true){
       memset(values, 0, MAX_N);

       std::cin >> n >> x;
       
       if(n + x == 0) break;
       
       for(int i = 0; i < n; ++i)
           std::cin >> values[i];

       solve();
   }
   return 0;
}

void initialize(){
    memset(is_prime_number, true, MAX_X);
    is_prime_number[0] = false, is_prime_number[1] = false;
    for(int i = 2; i <= 1000; ++i){
        if(is_prime_number[i]){
            for(int j = i + 1; j < MAX_X; ++j){
                if(j % i == 0)
                    is_prime_number[j] = false;
            }
        }
    }
}

void solve(){
   int ans = 0;
   int dp[MAX_X];
   memset(dp, 0, MAX_X);

   /*
   std::cout << "x : " << x << std::endl << "n : " << n << std::endl;
   for(int i = 0; i < (x > 1000 ? 1000 : x); ++i){
       std::cout << i << " dp : " << dp[i] << std::endl;
   }
   */

   for(int i = 1; i <= x; ++i){
       int res = 0;
       for(int j = 0; j < n; ++j){
           if(values[j] <= i){
               res = std::max(dp[i - values[j]] + values[j], res);
           }
       }
       dp[i] = std::max(dp[i], res);
       if(is_prime_number[dp[i]]){
           ans = std::max(dp[i], ans);
       }
   }

   if(ans != 0){
       std::cout << ans << std::endl;
   }
   else{
       std::cout << "NA" << std::endl;
   }

}

C++: #include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int n;//料理の種類
int x;
int sum;
bool prime[1000001];
bool check[1000001];
int main()
{

  for(int i = 0;i <1000001;i++){
    prime[i] = true;
    check[i] = false;
  }
  prime[0] = false;
  prime[1] = false;
  for(int i = 2;i <1000001;i++){
    if(prime[i]){
      for(int j = 2*i;j <1000001;j+=i){
	prime[j]= false;
      }
    }
  }
  while(cin>>n>>x,n||x){
    bool flag1=false;
    int dish[30];
   
    for(int i = 0;i < n;i++){
      cin>>dish[i];
    }
    check[0] =true;//0はどの料理からでも作れる
    for(int i = 0;i <=x;i++){
      if(check[i]){
	for(int j = 0;j <n;j++){
	  if(i + dish[j]<=x)
	    check[i+dish[j]] = true;
	}
      }
    }
    int ans = 0;

    for(int i =x;i >0;i--){//上から調べる
      if(check[i]&&prime[i]){
	flag1 = true;
	ans = i;
	break;
      }
    }
    if(flag1)
      cout <<ans<<endl;
    else
      cout <<"NA"<<endl;
  }

  return 0;
}

C++: #include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
#include <list>
using namespace std;
#define INF 100000000
typedef long long int lli;
typedef pair<int,int> P;
bool dp[1000001];
bool pn[1000001];

void eratos(bool f[]){
	for(int i=0; i<1000001; ++i){
		f[i]=true;
	}
	pn[0]=false;
	pn[1]=false;
	for(int i=2; i*i<1000001; ++i){
		if(f[i]){
			for(int j=2; i*j<1000001; ++j){
				f[i*j]=false;
			}
		}
	}
}
int main(){
	int n,x;
	eratos(pn);
	while(cin >> n >> x){
		if(n==0&&x==0) break;
		vector<int> cost(n);
		for(int i=0; i<=x; ++i){
			dp[i]=false;
		}
		for(int i=0; i<n; ++i){
			cin >> cost[i];
			dp[cost[i]]=true;
		}
		for(int i=0; i<n; ++i){
			for(int j=0; j<=x; ++j){
				if(dp[j]&&j+cost[i]<=x){
					dp[j+cost[i]]=true;
				}
			}
		}
		bool flag=false;
		int ans;
		for(int i=x; i>=0; --i){
			if(dp[i]&&pn[i]){
				flag=true;
				ans=i;
				break;
			}
		}
		if(flag) {
			cout << ans << "\n";
		} else {
			cout << "NA\n";
		}
	}
	return 0;
}