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>
#include <algorithm>
using namespace std;
#define MAX 1000001

bool is_prime[MAX];

void Sieve() {
  
  is_prime[0] = is_prime[1] = 0;
  for(int i=2; i<MAX; i++) is_prime[i] = 1;
  
  for(int i=2; i*i<MAX; i++) {
    if(is_prime[i]) {
      for(int j=2*i; j<MAX; j+=i) {
	is_prime[j] = 0;
      }
    }
  }
}

int main() {
  
  Sieve();
  
  int n, a, b;
  while(cin >> n >> a, n+a) {
    bool c[MAX] = {};
    c[0] = 1;
    for(int i=0; i<n; i++) {
      cin >> b;
      for(int j=b; j<MAX; j++) {
	c[j] = c[j] | c[j-b];
      }
    }
    
    int mx = -9999;
    for(int i=0; i<=a; i++) {
      if(c[i] && is_prime[i]) mx = max(mx, i);
    }
    if(mx == -9999) cout << "NA" << endl;
    else cout << mx << endl;
  }
  
  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <vector>
#include <cmath>

using namespace std;

vector<int> primes;

void make_primes( int lim ) {
  vector<bool> vs( lim + 1 );
  fill( vs.begin(), vs.end(), true );
  vs[ 0 ] = vs[ 1 ] = false;
  const int l = (int)sqrt( lim );
  for ( int i = 2; i <= l; i++ ){
	if ( vs[ i ] ) {
	  for ( int j = i * i; j <= lim; j += i ) {
		vs[ j ] = false;
	  }
	}
  }
  for ( int i = 2; i <= lim; i++ ) {
	if ( vs[ i ] ) {
	  priems.push_back( i );
	}
  }
}

bool isPrime( int n ) {
  return binary_search( primes.begin(), primes.end(), n );
}

int main() {
  make_primes( 1000000 );
  while( true ) {
	int n, x;
	cin >> n >> x;
	if ( n == 0 and x == 0 ) break;
	vector<int> vs( n );
	for ( int i = 0; i < n; i++ ) {
	  cin >> vs[ i ];
	}
	sort( vs.begin(), vs.end() );
	vector<int> cs;
	cs.push_back( 0 );
	vector<int> indices( n );
	fill( indices.begin(), indices.end(), 0 );
	while( cs.back() <= x ) {
	  int mv = 100000000;
	  int mi = -1;
	  for ( int i = 0; i < n; i++ ) {
		if ( mv > cs[ indices[ i ] ] + vs[ i ] ) {
		  mi = i;
		  mv = cs[ indices[ i ] ] + vs[ i ];
		}
	  }
	  if ( cs.back() < mv ) {
		cs.push_back( mv );
	  } 
	  indices[ mi ]++;
	}
	reverse( cs.begin(), cs.end() );
	bool s = false;
	for ( int v : cs ) {
	  if ( isPrime( v ) ) {
		s = true;
		cout << v << endl;
		break;
	  }
	}
	if ( not s ) {
	  cout << "NA" << endl;
	}
  }
}

C++: #include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

void makePrimeNumber(int N, vector<bool>& prime) // 0ツ暗按湘」Nツ暗按可コツづ個青ョツ青板つゥツづァツ素ツ青板づーツ探ツつキ
{
    prime.assign(N+1, true);
    prime [0] = prime[1] = false;
    for(int i=2; i*i<=N; i++){
        if(prime[i]){
            for(int j=i; i*j<=N; j++){
                prime[i*j] = false;
            }
        }
    }
}

int main()
{
    vector<bool> prime;
    makePrimeNumber(1000000, prime);

    for(;;){
        int n, x;
        cin >> n >> x;
        if(n == 0)
            return 0;

        vector<bool> value(x+1, false);
        value[0] = true;
        for(int i=0; i<n; ++i){
            int a;
            cin >> a;
            for(int j=0; j+a<=x; ++j){
                if(value[j])
                    value[j+a] = true;
            }
        }

        int i = x;
        while(i > 0 && (!value[i] || !prime[i]))
            -- i;
        if(i == 0)
            cout << "NA" << endl;
        else
            cout << i << endl;
    }
}

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

int K[KMAX];
unsigned char T[KMAX][VMAX+1];

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

    int k, v;
    while( cin >> k >> v && k && v ){
	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 >= 2; i-- ){
	    if ( prime[i] && T[k-1][i] ) { ans = i; break; }
	}
	
	if ( ans == -1 ) cout << "NA" << endl;
	else cout << ans << endl;
    }
}

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[30][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;
	while(cin >> n >> x){
		if(n==0&&x==0) break;
		vector<int> cost(n);
		for(int i=0; i<n; ++i){
			cin >> cost[i];
		}
		for(int i=0; i<n; ++i){
			for(int j=0; j<=x; ++j){
				dp[i][j]=false;
			}
		}
		for(int i=0; i*cost[0]<=x; ++i){
			dp[0][cost[0]*i]=true;
		}
		for(int i=1; i<n; ++i){
			for(int j=0; j<=x; ++j){
				if(dp[i-1][j]){
					for(int k=0;j+cost[i]*k<=x ; ++k){
						dp[i][j+cost[i]*k]=true;
					}
				}
			}
		}
		eratos(pn);
		bool flag=false;
		int ans;
		for(int i=x; i>=0; --i){
			if(dp[n-1][i]&&pn[i]){
				flag=true;
				ans=i;
				break;
			}
		}
		if(flag) {
			cout << ans << "\n";
		} else {
			cout << "NA\n";
		}
	}
	return 0;
}