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 <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 = 2;
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<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 1000000

bool prime[MAX];
bool order[MAX+1];
int menu[30];
int n,money;

void init(){
	fill(prime,prime+MAX,true);
	prime[0]=prime[1]=false;
	for(int i=2;i<MAX;i++){
		if(prime[i]){
			for(int j=2;j*i<MAX;j++)
				prime[j*i]=false;
		}
	}
}
int main(){
	init();
	while(cin>>n>>money,n|money){
		for(int i=0;i<n;i++)cin>>menu[i];
		fill(order,order+(MAX+1),false);
		order[0]=true;
		for(int i=0;i<=money;i++){
			for(int j=0;j<n;j++){
				if(order[i] && i+menu[j]<=money)
					order[i+menu[j]] = true;
			}
		}
			
		int ans=-1;
		for(int i=money;i>1;i--){
			if(prime[i] && order[i]){
				ans=i;
				break;
			}
		}
		if(ans!=-1)cout<<ans<<endl;
		else cout<<"NA"<<endl;
	}
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999


bool era[10000100]={false};


void makeERA(){
    for(int i=2;i<10000001;i++){
        if(era[i]==true){
            int x=10000000/i;
            for(int j=2;j<=x;j++){
                era[i*j]=false;
            }
        }
    }
    era[2]=true;
}


int main(){
    for(int i=0;i<10000101;i++)era[i]=true;
    era[0]=false;era[1]=false;
    makeERA();

    int n,x;
    while(cin>>n>>x){
        if(n==0&&x==0)break;
        vector<int> data(n);
        rep(i,n) cin>>data[i];
        
        static bool dp[1000100];
        rep(i,1000100)dp[i] = false;
        dp[0] = true;
        
        rep(i,n){
            int val = data[i];
            rep(j,x+1){
                if(j-val>=0) dp[j] |= dp[j-val];
            }
        }
        for(int i=x;i>=0;i--){
            if(era[i]&&dp[i]){
                cout<<i<<endl;
                goto next;
            }
        }
        cout<<"NA"<<endl;
    next:;
    }
}

C++: #include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 10007;
static const int INF = 1 << 25;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0,  1, -1,  1, -1 };
static const int dy[] = { 0, -1, 0, 1 , 1,  1, -1, -1 };

static vector<bool> is_pm( 10000001, true );;
static bool dp[ 31 ][ 10000001 ];
static int ans = 0, n, m;
static VI ar;

static void solve( const int now, const int how_much ) {
	if ( how_much > m  ) {
		return;
	}
	if ( is_pm[ how_much ] ) {
		ans = max( ans, how_much );
	}
	if ( now == n || dp[ now ][ how_much ] ) {
		return;
	}
	
	dp[ now ][ how_much ] = true;
	solve( now, how_much + ar[ now ] );
	solve( now + 1, how_much );
}

int main() {
	for ( int i = 2; i * i < 10000000; i++ ) {
		if ( is_pm[ i ] ) {
			for ( int j = i * i; j <= 10000000; j += i ) {
				is_pm[ j ] = false;
			}
		}
	}
	is_pm[ 3 ] = false;
	is_pm[ 2 ] = false;
	is_pm[ 1 ] = false;
	is_pm[ 0 ] = false;
	while ( ~scanf( "%d %d", &n, &m ) && n && m ) {
		ar.resize( n );
		ar.reserve( n );
		for ( int i = 0; i < n; i++ ) {
			scanf( "%d", &ar[ i ] );
		}
		memset( dp, false, sizeof( dp ) );
		ans = 0;
		solve( 0, 0 );
		if ( ans == 0 ) {
			printf( "NA\n" );
		}
		else {
			printf( "%d\n", ans );
		}
	}
	return 0;
}