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>


const int MAX = 1000001;

using namespace std;

int prime[MAX];

void make(void){

  fill(prime,prime+MAX,1);
  prime[0] = 0;
  prime[1] = 0;
  for(int i = 2; i < MAX; i++){
    if(prime[i]){
      for(int j = 2*i; j < MAX; j+=i){
	prime[j] = 0;
      }
    }
  }
}

int main(){
  make();
  int menu, money;

  while(cin >> menu >> money && menu && money){

    int data[money+1];
    fill(data,data+money+1,0);
    int price[menu];

    for(int i = 0; i < menu; i++){
      cin >> price[i];
      for(int j = price[i]; j <= money; j+=price[i]){
	data[j] = 1;
      }
    }

    for(int i = 0; i < menu; i++){
      for(int j = price[i]; j <= money; j++){
	if(data[j-price[i]]) data[j] = 1;
      }
    }
    for(int i = money; i >= 0; i--){
      if(i == 0) cout << "NA" << endl;
      if(data[i] && prime[i]){
	cout << i << endl;
	break;
      }
    }
  }
  return 0;
}

C++: #include <bits/stdc++.h>
#define all(a) (a).begin(),(a).end()
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
#define MAX 1000000+1
bool prime[MAX];

void sieve(){
  prime[0] = prime[1] = false;
  for(int i=2;i<MAX+1;i++)
    prime[i] = true;
  for(int i=2;i<MAX+1;i++)
    if(prime[i])
      for(int j=i*2;j<MAX+1;j+=i)
	prime[j]=false;
}

bool isPrime(int n){
  return prime[n];
}

void solve(int n, int x, const int *v){
  int dp[n+1][x+1];
  rep(i,n+1)
    dp[i][0]=0;
  rep(i,x+1)
    dp[0][i]=0;

  int max=0;
  for(int i=1;i<n+1;i++)
    for(int j=1;j<x+1;j++){
      int Do =  dp[i][j-v[i]]+v[i];
      int Not = dp[i-1][j];
      if(j<v[i-1])
	dp[i][j] = Not;
      else{
	if (Do > Not){
	  dp[i][j] = Do;
	  if(max<Do && isPrime(Do) && Do<=x)
	    max=Do;
	}
	else
	  dp[i][j] = Not;
      }
    }
  /*
  putchar('\n');
  rep(i,n+1){
    printf("%d :",i+1);
    rep(j,x){
      printf("%2d ",dp[i][j]);
    }
    putchar('\n');
  }
  */
   if(max)
    cout << max << endl;
  else
    cout << "NA" << endl;
}

int main(){
  sieve();
  int v[31];
  v[0]=0;
  for(;;){
    int n,x;
    cin >> n >> x;
    if(!(n+x)) break;
    for(int i=1;i<n+1;i++)
      cin >> v[i];
    solve(n,x,v);
  }
}

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

using namespace std;

const int MAX_N = 30;
const int MAX_X = 1000000 + 1;

int kin[MAX_N];
bool dp[MAX_X];

bool isPrime ( int n )
{
	for (int i = 2; i*i <= n; ++i) {
		if (n % i == 0) return false;
	}
	return n >= 2;
}

int main ( void )
{
	vector<int> prime;
	prime.push_back(2);
	for (int i = 3; i < MAX_X; i+=2) {
		if (isPrime(i)) { prime.push_back(i); }
	}

	int n, x;

	while (cin >> n >> x, n | x) {
		fill(dp, dp+x, false);
		for (int i = 0; i < n; ++i) {
			cin >> kin[i];
		}

		dp[0] = true;
		for (int i = 0; i < x; ++i) {
			if (!dp[i]) { continue; }
			for (int j = 0; j < n; ++j) {
				if (i+kin[j] <= x) {
					dp[i+kin[j]] = true;
				}
			}
		}

		int ans;
		for (ans = x; ans >= 0; --ans) {
			if (dp[ans] && binary_search(prime.begin(), prime.end(), ans)) {
				break;
			}
		}

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

	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
bool sosu(int n) {
  if (n <= 1)
    return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0)
      return false;
  return true;
}
int main() {
  int n, x;
  while (cin >> n >> x, n) {
    bool dp[1000001] = {};
    dp[0] = 1;
    int a[50];
    rep(i, n) { cin >> a[i]; }
    rep(i, n) rep(j, x) {
      if (j + a[i] < 1000001)
        if (dp[j])
          dp[j + a[i]] = 1;
    }
    for (int i = x; i > 1; i--) {
      if (dp[i])
        if (sosu(i)) {
          cout << i << endl;
          goto end;
        }
    }
    cout << "NA" << endl;
  end:;
  }
  return 0;
}

C++: #include<iostream>
#include<cstring>
#define SIZE 1000001
using namespace std;

int data[99];
bool p[SIZE];
int n, x;
int memo[SIZE];

void prime(){

  for(int i=2;i*i<SIZE;i++){
    if(!p[i]) for(int j=i+i;j<SIZE;j+=i) p[j] = true;
  }

}

int solve(int s){

  if(s > x) return 0;
  if(memo[s]) return memo[s];

  for(int i=0;i<n;i++) solve(s+data[i]);
  
  return memo[s] = s;
}
int main(){

  prime();

  while(true){
    cin >> n >> x;
    if(!n && !x) break;

    for(int i=0;i<n;i++) cin >> data[i];

    memset(memo, 0, sizeof(memo));

    solve(0);

    int ans = 0;
    for(int i=x;i>0;i--){
      if(!p[i] && memo[i] > 0){
	ans = i;
	break;
      }
    }

    if(ans) cout << ans << endl;
    else cout << "NA\n";

  }
}

C++: #include <iostream>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;

const int N = 1000000;

int prime[N+1];
int table[N+1];
int dish[30];
int n, x;
int max_val;

void setPrime()
{
	memset(&prime[0], 0, sizeof(int) * (N+1));
	prime[2] = 1;
	for(int i=2; i<=N; i++)
	{
		bool is_prime = true;
		int limit = sqrt(i);
		for(int k=2; k<=limit; k++)
		{
			if(i % k == 0)
			{
				is_prime = false;
				break;
			}	
		}
		
		if(is_prime)
		{
			prime[i] = 1;
		}
	}
}

void solve()
{
	int price;
	queue<int> q;
	q.push(0);
	
	while(!q.empty())
	{
		price = q.front();
		q.pop();
		
		if(price > x)
		{
			continue;
		}
		
		if(prime[price] == 1 && max_val < price)
		{
			max_val = price;
		}
		
		for(int k=0; k<n; k++)
		{
			int new_price = price + dish[k];
			if(table[new_price] == 0)
			{
				table[new_price] = 1;
				q.push(new_price);
			}
		}
	}
}

int main()
{
	setPrime();
	
	while( 1 )
	{
		cin >> n >> x;
		if(n==0 && x==0)
		{
			break;
		}
		
		clock_t t = clock();
		for(int i=0; i<n; i++)
		{
			cin >> dish[i];
		}
		
		memset(&table[0], 0, sizeof(int)*(N+1));
		max_val = 0;
		solve();
		
		if(max_val != 0)
		{
			printf("%d\n", max_val);
		}
		else
		{
			printf("NA\n");
		}
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
const int MAX_INT = 1000000;
bool er[1000001];
int n,x,ans;
int v[31];
int solve(int k,int m);
int memo[31][1000001];
int main(){
  memset(er,true,sizeof(er));
  for(int i=2;i<sqrt(MAX_INT);i++){
    if(er[i]){
      for(int j=0;i*(j+2)<MAX_INT;j++){
	er[i*(j+2)]=false;
      }
    }
  }
  while(1){
    cin >> n >> x;
    if(!n && !x)break;
    memset(memo,-1,sizeof(memo));
    for(int i=0;i<n;i++){
      cin >> v[i];
    }
    
    ans = solve(0,0);
    if(!ans)cout << "NA\n";
    else cout << ans << endl;
  }
}
int solve(int k,int m){
  if(memo[k][m] != -1)return memo[k][m];
  if(m > x)return 0;
  else if(k == n){
    if(m == 0)return 0;
    if(er[m])return m;
    else return 0;
  }
  return memo[k][m] = max(solve(k,m+v[k]),solve(k+1,m));
}