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>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <stack>
#include <list>

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,b,n) for(int i=b;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

bool dp[1000002], sosu[1000002];
int n, x;
int v[30];

void sosuu() {
  sosu[0]=false;
  sosu[1]=false;
  for(int i=2; i*i<=x; i++) {
    if (sosu[i]) {
      for (int j=2*i; j<=x; j+=i) {
        sosu[j] = false;
      }
    }
  }
}
  

int main() {
  while(cin >> n >> x, n) {
    rep(i, n)
      cin >> v[i];
    rep(i, x+1) {
      sosu[i] = true;
      dp[i] = false;
    }
    sosuu();
    rep(i, n) {
      dp[v[i]]=true;
      for(int j=v[i]; j<=x; j++)
        if(dp[j] && j+v[i] <= x)
          dp[j+v[i]] = true;
    }
    while(x>0) {
      if(dp[x] && sosu[x])
        break;
      x--;
    }
    if(x==0)
      cout << "NA" << endl;
    else
      cout << x << endl;
  }

  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
bool e[1000001],dp[1001110];
int main(){
  e[0]=e[1]=1;
  for(int i=2;i<1000001;i++)
    for(int j=i*2;j<1000001;j+=i)
      e[j]=1;
  int n,m;
  while(cin>>n>>m,n){
    for(int i=0;i<m+110;i++)dp[i]=0;
    int a[n],c=1,p;
    for(int i=0;i<n;i++)cin>>a[i];
    /*for(int i=0;i<n;i++)
      for(int j=1;j<=m;j++){
        if(dp[j]&&a[i]+j<=m)dp[a[i]+j]=1;
        if(a[i]*j<=m)dp[a[i]*j]=1;}
    for(p=m;p>=0;p--)if(dp[p]&&!e[p]){c=0;break;}
    if(c)cout<<"NA"<<endl;
  else cout<<p<<endl;*/
  }
}

C++: #include <iostream>
#define N 30
#define N1 1000001
using namespace std;
void DP();
int n,x,c[N];
bool prime[N1];
int main(){
  int i,j;
  for(i=0;i<=N1;i++) prime[i]=true;
  prime[0]=prime[1]=false;
  for(i=0;i<N1;i++){
    if(prime[i]==true){
      for(j=i*2;j<N1;j+=i){
	prime[j]=false;
      }
    }
  }
  while(1){
    cin >> n >> x;
    if(n==0&&x==0) break;
    for(i=0;i<n;i++){
      cin >> c[i];
    }
    DP();
  }
  return 0;
}
void DP(){
  int dp[N1],flag,ans,i,j;
  for(i=0;i<N1;i++) dp[i]=0;
  dp[0]=1;
  for(i=1;i<N1;i++){
    if(i%c[0]==0) dp[i]=1;
  }
  for(i=1;i<n;i++){
    for(j=1;j<N1;j++){
      if(dp[j]==0&&j>=c[i]){
	if(dp[j-c[i]]==1) dp[j]=1;
      }
    }
  }
  flag=0;
  for(i=x;i>=1;i--){
    if(dp[i]==1&&prime[i]==true){
      ans=i;
      flag=1;
      break;
    }
  }
  if(flag==1) cout << ans << endl;
  else cout << "NA" << endl;
}

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

int K[KMAX], T[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;
    for ( int i = 3; i*i <= n; 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[j] = 0;
	for ( int j = K[0]; j <= v; j += K[0] ) T[j] = 1;
	T[0] = 1;
	for ( int i = 1; i < k; i++ ){
	    for ( int j = K[i]; j <= v; j++ ){
		T[j] = (T[j] | T[j-K[i]]);
	    }
	}
	int ans = -1;
	for ( int i = v; i >= 2; i-- ){
	    if ( prime[i] && T[i] ) { ans = i; break; }
	}
	
	if ( ans == -1 ) cout << "NA" << endl;
	else cout << ans << endl;
    }
}

C++: #include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 28;

vector< bool > get_prime(int n){
  vector< bool > prime( n + 1, true);
 
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
 
  for(int i = 2; i * i <= n; i++){
    if(prime[i]){
      for(int j = i + i; j <= n; j += i) prime[j] = false;
    }
  }
 
  return prime;
}

int main(){
  int n, x;
  while(cin >> n >> x, n){
    vector< int > food(n);
    for(int i = 0; i < n; i++){
      cin >> food[i];
    }
    vector< bool > dp(x + 1, false);
    dp[0] = true;
    for(int i = 0; i <= x; i++){
      if(dp[i]){
        for(int j = 0; j < n; j++){
          if(i + food[j] > x) continue;
          dp[i + food[j]] = true;
        }
      }
    }
    vector< bool > prime = get_prime(x);
    int ret = -1;
    for(int i = x; i >= 0; i--){
      if(prime[i] && dp[i]){
        ret = i;
        break;
      }
    }
    if(~ret) cout << ret << endl;
    else cout << "NA" << endl;
  }
}

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

using namespace std;

int main(void){
	int n,lim;
	bool isprime[1000001];
	memset(isprime,true,sizeof(isprime));
	isprime[1] = false;
	for(int i=2;i<1000001;i++){
		if(isprime[i] == true){
			for(int j=2;j*i<1000001;j++){
				isprime[i*j] = false;
			}
		}
	}
	
	
	while(cin >> n >> lim){
		if((n|lim) == 0) break;
		vector<int> v;
		int tmp;
		bool creatable[lim+1];
		memset(creatable,false,sizeof(creatable));
		creatable[0] = true;
		
		for(int i=0;i<n;i++){
			cin >> tmp;
			v.push_back(tmp);
		}
		for(int i=0;i<lim;i++){
			if(creatable[i]){
				for(int j=0;j<v.size();j++){
					if(i+v[j] <= lim){
						creatable[i+v[j]] = true;
					}
				}
			}
		}
		
		for(int i=lim;i>=0;i--){
			if(i==0){
				cout << "NA" << endl;
				break;
			}
			if(isprime[i] && creatable[i]){
				cout << i << endl;
				break;
			}
		}
	}
}

C++: #include<vector>
#include<iostream>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()

const int N = 1000001;
const int M = 30;

bool table[M][N];
bool isprime[N];

void generate(){
  for(int i=0;i<N;i+=2)isprime[i]=false;
  for(int i=1;i<N;i+=2)isprime[i]=true;
  isprime[2]=true;
  for(int i=3;i*i <= N ;i+=2){
    if (isprime[i]){
      for(int j=2*i;j<N;j+=i)isprime[j]=false;
    }
  }
}

void solve(int n,int lim,vector<int> & price){
  rep(i,n)rep(j,lim+1)table[i][j]=false;
  
  for(int i=0;i<lim+1;i+=price[0]){
    table[0][i]=true;
  }

  REP(i,1,price.size()){
    rep(j,lim+1){
      table[i][j]=table[i-1][j];
      if (j-price[i] < 0)continue;
      //if (j-price[i] == 0)table[i][j]=true;
      table[i][j]|=(table[i][j-price[i]]|table[i-1][j-price[i]]);
    }
  }

  for(int i=lim;i>0;i--){
    if (isprime[i] && table[n-1][i]){
      cout << i << endl;
      return;
    }
  }
  cout << "NA" << endl;
}


main(){
  int n;
  int lim;
  generate();
  while(cin>>n>>lim && n){
    vector<int> a;
    int tmp;
    rep(i,n){
      cin>>tmp;
      a.push_back(tmp);
    }
    solve(n,lim,a);
  }
  return false;
}