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 <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<((x))<<endl
#define fi first
#define se second

#define INF 2147483600
#define long long long

const int MAX_PRIME = 1000000;
bool isPrime[MAX_PRIME+1];
// sieve of Erastosthenes
inline void prime_list(){
  const int sz = MAX_PRIME;
  fill(isPrime, isPrime+sz+1, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=4;i<=sz;i+=2) isPrime[i]=false;
  for(int i=3; i*i<=sz; i+=2){
    if(isPrime[i]){
      for(long j=(long)i*i; j<=sz; j+=i) isPrime[j]=false;
    }
  }
}

int main(){
  prime_list();
  int n,x;
  while(cin>>n>>x, n|x){
    vector<int> dish(n);
    rep(i,n) scanf("%d", &dish[i]);
    vector<bool> dp(x+1, false);
    dp[0]=true;
    rep(i,n){
      rep(j,x) if(dp[j]){
        if(j+dish[i]<=x) dp[j+dish[i]]=true;
      }
    }
    int res = -1;
    repl(i,2,x+1) if(isPrime[i] && dp[i]) res = i;
    if(res == -1 ) cout<<"NA" << endl;
    else cout << res << endl;
  }

  return 0;
}

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

const int LIMIT = 1000000;

int main()
{
	bool* prime = new bool[ LIMIT + 1 ]();
	prime[ 0 ] = prime[ 1 ] = true;
	for( int i = 2; i < LIMIT + 1; ++i ){
		if( prime[ i ] ) continue;
		for( int j = i + i; j < LIMIT + 1; j += i ){
			prime[ j ] = true;
		}
	}

	int n, x;
	while( cin >> n >> x && ( n || x ) ){
		bool* price = new bool[ x + 1 ]();
		set< int > menu;
		for( int i = 0; i < n; ++i ){
			int p;
			cin >> p;
			if( p <= x ){
				menu.insert( p );
				price[ p ] = true;
			}
		}
		int ans = 0;
		for( int i = 0; i <= x; ++i ){
			if( !price[ i ] ) continue;
			if( !prime[ i ] ){
				ans = i;
			}
			set< int >::iterator itr = menu.begin();
			while( itr != menu.end() ){
				int a = i + *itr;
				if( a <= x ){
					price[ a ] = true;
				}
				++itr;
			}
		}

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

		delete[] price;
	}

	delete[] prime;

	return 0;
}

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

int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    int menu[n];
    for(int i=0;i<n;i++)cin>>menu[i];
    bool money[x+1];
    money[0] = true;#include<iostream>
#include<algorithm>
using namespace std;

int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    int menu[n];
    for(int i=0;i<n;i++)cin>>menu[i];
    bool money[x+1];
    money[0] = true;
    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]]){
	  money[i] = true;
	  break;
	}
      }
    }
    int p = -1;
    for(int i=x;i>0;i--){
      if(money[i]&&prime[i]){
	p=i;
	break;
      }
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]]){
	  money[i] = true;
	  break;
	}
      }
    }
    int p = -1;
    for(int i=x;i>0;i--){
      if(prime[i]&&money[i]){
	p=i;
	break;
      }
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <cmath>
#define VMAX  1000000
using namespace std;

int main(){
  int k, v;
  bool prime[VMAX+1];
  for (int i=0;i<=VMAX;i++) prime[i] = false;
  for (int i=3;i<=VMAX;i+=2) prime[i] = true;
  prime[2] = true;
  int limit = (int)sqrt((double)VMAX) + 1;
  for (int i=3;i<=limit;i+=2){
    if (!prime[i]) continue;
    for (int j=i+i;j<=VMAX;j+=i)prime[j]=false;
  }

  while (cin >> k >> v && !(k ==0 && v ==0)){
    int K[k];
    char T[k][v+1];
    for (int i=0;i<k;i++) cin >> K[i];
    for (int j=0;j<=v;j++) T[0][j]=0;
    for (int j=K[0];j<=v;j+=K[0]) T[0][j]=1;

    for (int i=0;i<k;i++) T[i][0]=1;
    for (int i=1;i<k;i++){
      for (int j=1;j<K[i];j++) T[i][j] = T[i-1][j];
      for (int j=K[i];j<=v;j++){
        T[i][j] = (T[i-1][j] | T[i][j-K[i]]);
      }
    }
    int ans = -1;
    for (int i=v;i>1;i--){
      if (prime[i] && T[k-1][i]){
        ans = i;
        break;
      }
    }
    if (ans==-1)
      cout << "NA" << endl;
    else
      cout << ans << endl;
  }
  return 0;
}