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 <iostream>
#define MAX 1000001

using namespace std;

bool dp[MAX];
int n,est;
int value[31] = {0};


int isPrime(int N){

  for( int i = 2 ; i*i + 1 < N ; i++ ){
    if( N % i == 0 ) return 0;
  }
  return N;

}

void solve(void){

  dp[0] = 1;
  for( int i = 0 ; i < n ; i++ ){
    for( int j = value[i] ; j <= est ; j++ ){
      if( dp[j - value[i]] ) dp[j] = true;
    }
  }
  
}

int main(void){


  while( cin >> n >> est , n + est ){

    fill( dp , dp + MAX , false );

    for( int i = 0 ; i < n ; i++ )
      cin >> value[i];

    solve();

    int ans = 0;
    for( int i = est ; i >= 2 ; i-- ){
      if( dp[i] ){
	ans = isPrime(i);
	if( ans ) break;
      }
    }
    if( ans ) cout << ans << endl;
    else cout << "NA" << endl;

  }

  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

int Wm, N, W;
int w[1000];
bool dp[1000001];
deque< int > vc, newvc;
void rec( int mul){ // mul: 残りの重さ
  if(dp[mul]++) return;
  for(int i = 0; i < N; i++){
    if(mul + w[i] > W){
      newvc.push_back(mul + w[i]);
      continue;
    }
    rec(mul + w[i]);
  }
}
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(i){
    if(dp[i] && !isprime(i)) return i;
    i--;
  }
  return 0;
}
int main(){

  while(cin >> N >> Wm, N){
    fill_n( dp, Wm + 1, false);
    for(int i = 0; i < N; i++){
      cin >> w[i];
    }
    vc.push_back(0);
    for(W = 1000 ; W < Wm; W += 1000){
      for(int i = 0; i < !vc.empty() ; i++){
        rec(vc.front());
        vc.pop_front();
      }
      vc = deque<int>(newvc.begin(),newvc.end());
      newvc.clear();
    }
    W = Wm;
    for(int i = 0; !vc.empty() ; i++){
      rec(vc.front());
      vc.pop_front();
    }
    newvc.clear();
    int ret = solve(W);
    if(ret == 0) cout << "NA" << endl;
    else cout << solve(W) << endl;
    vc.clear();
  }
}

C++: #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <cmath>

using namespace std;

vector<int> price;
list<int> primes;

const int M = 1000000;
const int L = 30;
const int D = 100;
const int S = M/D;
pair<int,int> memo[S][L];

void mk_primes(int x)
{
	for( int i = 3; i <= x; i+=2 ) {
		for( int j = 3; j <= sqrt(i); j++ ) {
			if( i % j == 0 ) {
				goto NEXT;
			}
		}
		primes.push_front(i);
	NEXT:;		
	}
}

int solve(int x, int pos)
{
	pair<int,int>& pa = memo[x%S][pos];
	if( pa.first == x && -1 < pa.second )
		return pa.second;

	int result = 0;

	int p = price[pos++];
	int s = x / p;

	if( price.size() == pos ) {

		if( s*p == x ) {
			result = 1;
			// cout << "(" << p << "*" << s << ")";
		}
		
		
	} else {

		for( int i = 0; i <= s; i++ ) {

			int t = i * p;
			result = solve(x-t, pos);
			if( result ) {
				// cout << "(" << p << "*" << i << ")";
				break;
			}
		}
	}

	pa.first = x;
	pa.second = result;
	return result;
}

int main(int argc, char* argv[])
{
	while(1) {

		int n; cin >> n;
		int x; cin >> x;

		if( n == 0 && x == 0)
			break;
	
		for( int i = 0; i < n; i++ ) {
			int p; cin >> p;
			price.push_back(p);
		}

		mk_primes(x);

		for( int i = 0; i < S; i++ ) {
			for( int j = 0; j < L; j++ ) {			
				memo[i][j] = make_pair(-1,-1);
			}
		}

		for( auto p : primes ) {
			if( solve(p, 0) ) {
				cout << p << endl;
				goto LAST;
			}
		}

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}

C++: #include<cstdio>
#include<iostream>
using namespace std;
int main(){
	bool prime[1000001];
	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 = -1;
		for(int i = w; i >= 2; i--){
			if(!prime[i] && dp[i]){
				ans = i;
				break;
			}
		}
		if(ans == -1)puts("NA");
		else printf("%d\n",ans);
	}
	return 0;
}

C++: //19
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  static bool cmp[1000001]={true,true};
  for(int i=2;i<=1000000;i++){
    if(!cmp[i]){
      for(int j=2;i*j<=1000000;j++){
	cmp[i*j]=true;
      }
    }
  }
  for(int n,x;cin>>n>>x,n|x;){
    static bool ch[1000001];
    fill_n(ch,1000001,false);
    ch[0]=true;
    for(int i=0;i<n;i++){
      int p;
      cin>>p;
      for(int j=p;j<=x;j++){
	ch[j]|=ch[j-p];
      }
    }
    int ans;
    for(ans=x;ans;ans--){
      if(!cmp[ans]&&ch[ans])break;
    }
    if(ans){
      cout<<ans<<endl;
    }else{
      cout<<"NA"<<endl;
    }
  }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
bool dp[1000120];
bool notPrime[1000120];
int main(){
    notPrime[0] = notPrime[1] = true;
    for(int i = 2;i*i < 1000010;i++){
        for(int j = 2 * i;j < 1000010;j+=i){
            notPrime[j] = true;
        }
    }
    int n,x;
    while(cin>>n>>x,n){
        dp[0] = true;
        while(n--){
            int a;
            cin>>a;
            for(int i = 0;i <= x;i++){
                if(dp[i]&&i+a <= 100010)dp[i+a] = true;
            }
        }
        bool flg = false;
        for(int i = x;i >= 2;i--){
            if(!notPrime[i] & dp[i]){
                cout<<i<<endl;
                flg = true;
                break;
            }
        }
        if(!flg)cout<<"NA"<<endl;
        for(int i = 0;i < 1000020;i++)dp[i] = false;
    }
}

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 (j + a[i] < 1000001)
        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;
}