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])
		if n == 0 && x == 0 {
			break
		}
		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;

int pri[1000001];
int price[31];
int n,x;
int dp[31][1000001]; 
int dps(int i,int sum_m){
  int ss=0;
  int ans;
  if(dp[i][sum_m]!=-1)
    {
      return dp[i][sum_m];
    }
  if(i>=n)
    return 0;
  if(sum_m>=x)
    return 0;
  //  cout<<sum_m<<endl;
  if(pri[price[i]+sum_m]==1 && ans<price[i]+sum_m &&sum_m+price[i]<=x)
    {
      ans=price[i]+sum_m;
      if(ss<ans)
	ss=ans;
    }
  ans= dps(i,price[i]+sum_m);
  if(ss<ans)
    ss=ans;
  ans = dps(i+1,sum_m);
  if(ss<ans)
    ss=ans;
  dps(i+1,sum_m+price[i]);
  if(ss<ans)
    ss=ans;
  
  dp[i][sum_m]=ss;
  //  cout<<ss<<endl;
  return ss;
}

int main()
{
  int ans;
  fill(pri,pri+1000001,1);
  for(int i=2;i<1000001/2;i++)
    {
      for(int x=i+i;x<1000001;x+=i)
	pri[x]=0;
    }
  for(;cin>>n>>x,n;)
    {
      for(int i=0;i<n;i++)
	{
	  cin>>price[i];
	}
      for(int i=0;i<31;i++)
	for(int j=0;j<1000001;j++)
	  dp[i][j]=-1; 
      ans=dps(0,0);
      if(ans==0)
	cout<<"NA"<<endl;
      else
	cout<<ans<<endl;
    }
  
  
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <limits>
#include <cstring>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

#define LIMIT 1000011
using namespace std;

typedef pair<int, int> paii;
typedef long long ll;

bool isnotprime[LIMIT] = {0};
bool dp[30][LIMIT] = {0};
int n, x;
int dishes[100];

void erathos()
{
	CLR(isnotprime);
	
	FOR(i, 2, LIMIT)
	{
		if( !isnotprime[i] )
		{
			for(int j = 2; i*j < LIMIT; j++)
			{
				isnotprime[i*j] = true;
			}
		}
	}
}

int solve()
{
	int res = 0;
	
	CLR(dp);
	
	FOR(j, 0, n)
	{
		for(int i = dishes[j]; i < LIMIT; i += dishes[j])
		{
			dp[j][i] = true;
		}
		
		if( j > 0 )
			for(int i = 1; i < LIMIT; i++)
			{
				if( dp[j-1][i] )
					dp[j][i] = true;
				
				if(  i - dishes[j] > 0 && dp[j-1][i - dishes[j]] )
				{
					dp[j][i] = true;
				}
			}
	}
	
	RFOR(i, 0, x+1)
	{
		if( !isnotprime[i] && dp[n-1][i] )
		{
			res = i;
			break;
		}
	}
	
	return res;
}

int main()
{
	erathos();
	
	while(cin >> n >> x, (n||x))
	{
		FOR(i, 0, n)
		{
			cin >> dishes[i];
		}
		
		int r = solve();
		
		if(r != 0)
			cout << r << endl;
		else
			cout << "NA" << endl;
	}
		
	return 0;
}

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

using namespace std;

int main()
{
	vector<bool> era(1000000,true);
	era[0]=false;
	for(int i=2;i<1000;i++){
		if(era[i])	for(int j=i*i;j<1000000;j+=i)	era[j]=false;
	}

	for(int n,bud;cin>>n>>bud,n;){
		vector<int> menu(n);
		for(int i=0;i<n;i++)	cin>>menu[i];

		vector<bool> knap(bud+1);
		knap[0]=true;
		for(int i=0;i<n;i++){
			for(int j=0;j<bud;j++){
				if(knap[j] && j+menu[i]<=bud)
					knap[j+menu[i]]=true;
			}
		}

		bool b=false;
		for(int i=bud;i>=0;i--){
			if(knap[i] && era[i]){
				cout<<i<<endl;
				b=true;
				break;
			}
		}
		if(!b)	cout<<"NA"<<endl;
	}

	return 0;
}

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