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>
using namespace std ;
void ans( int cnt ,int dp[] )
{
	int a = cnt + 1 ;
	LOOK :
	a-- ;
	while( dp[ a ] != 1 )
	{
		a-- ;
		if( a < 2 )
		{
			END :
			cout << "NA" << endl ;
			return ;
		}
	}
	if( a < 2 )
	{
		goto END ;
	}
	if( a % 2 == 0 )
	{
		goto LOOK ;
	}
	if( a == 2 )
	{
		cout << a << endl ;
		return ;
	}
	for( int i = 3 ; i * i <= a ; i += 2 )
	{
		if( a % i == 0 )
		{
			goto LOOK ;
		}
	}
	cout << a << endl ;
	return ;
}
int main()
{
	int n ,m ;
	int dmon[ 30 ] ;
	int j ;
	while( cin >> n >> m )
	{
		if( n== 0 && m == 0 )
		{
			break ;
		}
		int cnt = m ;
		int dp[ 1000000 ] = { 0 } ;
		for( int i = 0 ; i < n ; i++ )
		{
			cin >> dmon[ i ] ;
		}
		for( int i = 0 ; i + dmon[ 0 ] <= m ; )
		{
			for( j = 0 ; j < n && i + dmon[ j ] <= m ; j++ )
			{
				dp[ i + dmon[ j ] ] = 1 ;
			}
			i++ ;
			while( dp[ i ] != 1 )
			{
				i++ ;
			}
		}
		ans( cnt ,dp ) ; 
	}
	return 0 ;
}

C++: #include<stdio.h>
int n,x;
int kin;
int i,j;
int dp[1000050],flg[1000050];
int main(void){
	for(i=1;i<=1000001;i++){
		flg[i]=1;
	}
	for(i=2;i*i<=1000001;i++){
		if(flg[i]==1){
			for(j=2;j*i<=1000001;j++){
				flg[i*j]=0;
			}
		}
	}
	scanf("%d %d",&n,&x);
	while(n!=0 && x!=0){
		for(j=0;j<=x;j++){
			dp[j]=-1;
		}
		dp[0]=0;
		for(i=0;i<n;i++){
			scanf("%d",&kin);
			for(j=0;j<=x;j++){
				if(dp[j]!=-1){
					dp[j+kin]=1;
				}
			}
		}
		int max=0;
		for(i=0;i<=x;i++){
			if(dp[i]==1 && flg[i]==1){
				max=i;
			}
		}
		if(max==0){
			printf("NA\n");
		}
		else {
			printf("%d\n",max);
		}
		scanf("%d %d",&n,&x);
	}
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef tuple<int, int> duo;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int Mod = 1000000000 + 0;
//{{{ templates
#define TT_ template<typename T>inline
#define TTF_ template<typename T,typename F>inline
TT_ T sq(T x){return x*x;}
TT_ T In(){T x;cin>>x;return x;}
TT_ void Out(T&x){cout<<x;}
TT_ void sort(T&v){sort(begin(v),end(v));}
TT_ void revs(T&v){reverse(begin(v),end(v));}
TT_ void uniq(T&v){sort(v);v.erase(unique(begin(v),end(v)),end(v));}
TT_ int ubnd(T&v,typename T::value_type x){return upper_bound(begin(v),end(v),x)-begin(v);}
TT_ int lbnd(T&v,typename T::value_type x){return lower_bound(begin(v),end(v),x)-begin(v);}
TTF_ void inpt(T&v,int n,F f){for(v.reserve(n);n--;v.emplace_back(f()));}
TTF_ void show(T&v,F f,string d=" ",string e="\n"){int i=0;for(auto&x:v)i++&&(cout<<d),f(x);cout<<e;}
TT_ typename T::iterator minel(T&v){return min_element(begin(v),end(v));}
TT_ typename T::iterator maxel(T&v){return max_element(begin(v),end(v));}

inline void fast_io(){ios_base::sync_with_stdio(0);cin.tie(0);}
inline int in(){int x;scanf("%d",&x);return x;}
inline ll pow_mod(ll a,ll k,ll m){ll r=1;for(;k>0;a=a*a%m,k>>=1)if(k&1)r=r*a%m;return r;}
inline ll mod_inv(ll a,ll p){return pow_mod(a,p-2,p);}
//}}} priority_queue queue deque front stringstream max_element min_element insert count make_tuple

const int MAX_N = 10100100;
int dp[MAX_N];
bool sieve[MAX_N];

int main()
{
  sieve[0] = sieve[1] = true;
  for (int i = 2; i * i <= MAX_N; i++){
    if (sieve[i]) continue;
    for (int j = i * i; j <= MAX_N; j += i){
      sieve[j] = true;
    }
  }

  int n, x, K = 1;
  while (n = in(), x = in(), n){
    int ans = -1;

    dp[0] = K;
    for (int i = 0; i < n; i++){
      int cost = in();
      for (int j = 0; j + cost <= x; j++){
        if (dp[j] == K){
          dp[j + cost] = K;
          if (!sieve[j + cost]) ans = max(ans, j + cost);
        }
      }
    }
    K++;
    if (ans < 0) puts("NA");
    else printf("%d\n", ans);
  }
  return 0;
}

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

using namespace std;

const int MAX_N = 1e6 + 10;

bool is_prime[MAX_N + 1];

void SieveOfEratosthenes(int n)
{
    for (int i = 0; i <= n; ++i)
        is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false;
}


int main()
{
    int n, x;

    SieveOfEratosthenes(1000000);

    while (cin >> n >> x, n || x) {
        int item[n];
        bool flag[x + 1];

        memset(flag, 0, sizeof(flag));
        for (int i = 0; i < n; ++i)
            cin >> item[i];

        flag[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j + item[i] <= x; ++j)
                if (flag[j])
                    flag[j + item[i]] = true;
        }

        int money = x;
        for ( ; money >= 0; --money)
            if (is_prime[money] && flag[money])
                break;

        if (money > 0)
            cout << money << endl;
        else
            cout << "NA\n";
    }

    return 0;
}

C++: #include<stdio.h>
#include<string.h>
int prime(int);
int p[1000001]={};
int main(){
	int n,x,v[30],i,j,o,a;
	while(1){
		memset(p,0,sizeof(p));
		memset(v,0,sizeof(v));
		scanf("%d %d",&n,&x);
		if(n==0&&x==0){
			break;
		}
		for(i=0;i<n;i++){
			scanf("%d",&v[i]);
			p[v[i]]=1;
		}
		for(i=0;i<=x;i++){
			if(p[i]){
				for(j=0;j<n;j++){
					if(i+v[j]<=x){
						p[i+v[j]]=1;
					}
				}
			}
		}
		o=0;
		for(i=x;i>=0;i--){
			if(p[i]){
				if(prime(i)){
					o=1;
					break;
				}
				
			}
		}
		if(o){
			printf("%d\n",i);
		}
		else{
			printf("NA\n");
		}
	}
	return 0;
}
int prime(int x){
	int i;
	if(x<2) return 0;
	else if(x==2) return 1;
	if(x%2==0) return 0;
	for(i=3;i*i<=x;i+=2){
		if(x%i==0) return 0;
	}
	return 1;
}

C++: 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define INF (1<<20)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

ll arr[1000010];

void Eratosthenes(int n) 
{
	rep(i, n+1)arr[i] = 1;
	for (int i = 2; i <= sqrt(n); i++) {
		if (arr[i]) {
			for (int j = 0; i*(j + 2) <= n; j++)
				arr[i*(j + 2)] = 0;
		}
	}
}

int dp[1000001];
int a[31], c[31];

int main()
{
	int n,x;
	cin >> n >> x;

	Eratosthenes(x);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		c[i] = 1000000 / a[i];
	}

	memset(dp,-1,sizeof(dp));
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= x; j++) {
			if (dp[j] >= 0) {
				dp[j] = c[i];
			}
			else if (j < a[i] || dp[j - a[i]] <= 0) {
				dp[j] = -1;
			}		  
			else {
				dp[j] = dp[j - a[i]] - 1;
			}
		}
	}
	
	for (int i = x; i >= 2; i--) {
		if (dp[i] >= 0) {
			if (arr[i]) {
				cout << i << endl;
				return 0;
			}
		}
	}
	cout << "NA" << endl;
	return 0;
}