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>

using namespace std;

bool prime[1100000];
int cooking[30];
int dp[30][1100000];
int nn, x;


int dfs(int n, int m)
{
  int res = 0;
  if(dp[n][m] != -1)
    return dp[n][m];
  
  if(m + cooking[n] <= x)
  {
    res = max(dfs(n, m + cooking[n]), n < nn - 1 ? dfs(n + 1, m + cooking[n]) : 0);
  }
  else if(n == nn - 1)
  {
    if(!prime[m])
      return m;
    else
      return 0;
  } 
  
  if(n < nn - 1)
    res = max(res, dfs(n + 1, m));
  
  dp[n][m] = res;

  return res;
}

void cal_prime()
{
  prime[1] = true;
  for(int i = 2; i < 1100000; i++)
  {
    if(prime[i])
    {
      
      continue;
    }
    int j = i * 2;
    for(; j < 1100000; j += i)
      prime[j] = true;
  }
}

int main()
{
  cal_prime();
  while(1)
  {
    for(int i = 0; i < 30; i++)
    {
      for(int j = 0; j < 1100000; j++)
        dp[i][j] = -1;
    }

    cin >> nn >> x;
    if(nn == 0 && x == 0)
      break;

    for(int i = 0; i < nn; i++)
      cin >> cooking[i];

    int ans = dfs(0, 0);
    if(!ans)
      cout << "NA" << endl;
    else
      cout << ans << endl;
  }
}

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+1];

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

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

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

  for(int i=1;i<=n;i++)
    rep(j,x+1){
      int Not = dp[i-1][j];
      int Do  = dp[i-1][j-v[i-1]]+v[i-1];
      if(j<v[i])
	dp[i][j] = Not;
      else{
	if(isPrime(Do) && Do > Not)
	  dp[i][j]=Do;
	else
	  dp[i][j] = Not;
      }
    }
  if(dp[n][x])
    cout << dp[n][x] << endl;
  else
    cout << "NA" << endl;
}

int main(){
  sieve();
  for(;;){
    int n,x;
    cin >> n >> x;
    if(!(n+x)) break;
    int v[30];
    rep(i,n)
      cin >> v[i];
    solve(n,x,v);
  }
}

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;
}

C++: #include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> PI;
#define MAX 1000009
/*void dfs(int num){
    if(flag) return;
    if(ans==num){flag=true;return;}
    if(num>ans){memo[num]=false;return;}
    else rep(i,n){
        cout<<num<<endl;
      if(num+v[i]<=ans&&memo[num+v[i]])dfs(num+v[i]);
    }
    memo[num]=false;
    return;
}*/
int main(){
    vector<bool>check(MAX+1);  //index number will be checked
    rep(i, MAX+1)check[i] = true;
    vector<int>Primenumber(MAX+1,0); //Primearray
    int counter =0;                  //Primearray counter;
    for(int i = 2; i<MAX+1;i++){
        if(check[i]){
            for(int j = 2;i*j<MAX;j++)
                check[i*j] = false;//?´???°??????Primearray???????´??????????????????°?????¨???false???
            Primenumber[counter] = i;
            counter++;
        }
    }
    int m,n,ans; bool flag;
    while(cin>>n>>m,n+m){
        vi v;
        int temp;
        flag=false;
        rep(i,n){cin>>temp; v.push_back(temp);}
        for(int i=m;i>=2;i--){
            if(check[i]){
                ans=i;break;}
        }
        bool array[MAX]; rep(i,MAX)array[i]=false;
        rep(i,n)array[v[i]]=true;
        for(int i=2;i<=ans;i++) {
            if(array[i])rep(j,n)if(i+v[j]<=ans)array[i+v[j]]=true;
            if(array[ans])break;
        }
        if(array[ans]) cout<<ans<<endl;
        else cout<<"NA"<<endl;
    }
}

C++: #include <iostream>
#include <string.h>
using namespace std;

bool prime[1000001];
void is_prime(int n){
	for(int i = 0; i <= n; ++i)
		prime[i] = true;
	prime[0] = prime[1] = false;
	
	for(int i = 2; i <= n; ++i){
		if(prime[i]){
			for(int j = i * 2; j <= n; j += i)
				prime[j] = false;
		}
	}
}

int memo[1000001];
int N, X, cook[50], ans;

int rec(int w){
	if(memo[w] != -1)
		return memo[w];
	if(X - w < 0)
		return 0;
	if(prime[X - w])
		ans = max(ans, X - w);
	int res = 0;
	for(int i = 0; i < N; ++i){
		if(w - cook[i] >= 0)
			res = max(res, rec(w - cook[i]));
	}
	return memo[w] = res;
}

int main() {
	is_prime(1000000);
	while(cin >> N >> X && (N || X)){
		ans = 0;
		memset(memo, -1, sizeof(memo));
		
		for(int i = 0; i < N; ++i)
			cin >> cook[i];
			
		rec(X);
		if(ans == 0)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
	
	
	return 0;
}