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 <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

vector<int> ch(10001, 1);

int check(int m){
	FOR(i, 2, sqrt(m)){
		if(m%i==0) return 0;
	}
	
	return 1;
}

int main(){
	ch[0]=ch[1]=0;
	FOR(i, 2, 10001){
		if(ch[i]==0) continue; 
		
		for(int j=2*i; j<=10000; j+=i){
			ch[j]=0;
		}
	}
	
	while(1){
		int n, x;
		scanf("%d%d", &n, &x);
		if(n==0) return 0;
		
		vector<int> v(n);
		REP(i, n) scanf("%d", &v[i]);
		
		vector<vector<int> > dp(n+1, vector<int>(x+1, -1));
		dp[0][0]=0;
		REP(i, n){
			REP(j, x+1){
				if(dp[i][j]!=-1){
					dp[i+1][j]=dp[i][j];
				}
				else {
					if(j>=v[i] && dp[i+1][j-v[i]]!=-1){
						if(j<=10000) dp[i+1][j]=ch[j];
						else dp[i+1][j]=check(j);
					}
				}
			}
		}
		
		int ans=-1;
		REP(i, x+1) if(dp[n][i]==1) ans=i;
		
		if(ans!=-1) cout << ans << endl;
		else cout << "NA" << endl;
	}
}

C++: #include <iostream>

using namespace std;

bool p[1000001];

void primes() {
    for (int i = 0; i < 1000001; i++) {
        p[i] = true;
    }
    
    p[0] = p[1] = false;
    
    for (int i = 2; i < 1000001; i++) {
        if (p[i]) {
            for (int j = i * 2; j < 1000001; j += i) {
                p[j] = false;
            }
        }
    }
}

int main() {
    int n, x;
    primes();

    while (true) {
        cin >> n >> x;
        if (!n && !x) break;
        
        bool dp[1000001] = {false};
        int dishes[30];

        for (int i = 0; i < n; i++) {
            cin >> dishes[i];
            dp[dishes[i]] = true;
        }

        for (int i = 0; i < 1000001; i++) {
            for (int j = 0; j < n; j++) {
                if (i - dishes[j]  >= 0) {
                    if (dp[i - dishes[j]]) {
                        dp[i] = true;
                        break;
                    }
                }
            } 
        }

        int max = 0;
        for (int i = 0; i <= x; i++) {
            if (p[i] && dp[i]) max = i;
        }

        if (max) {
            cout << max << endl;
        } else {
            cout << "NA" << endl;
        }
        
    }

    return 0;
}

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

bool so[1000001];

int main(void)
{
	so[0] = so[1] = true;
	// 素数表 true = 素数じゃない
	for(int i = 2; i <= 1000000; i++){
		for(int j = i*2; j <= 1000000; j+=i){
			so[j] = true;
	
		}
	}

	int N,M;

	while(cin >> N >> M, N | M){
		bool d[1000001] = {};
		d[0] = true;

		int mo;
		for(int i = 0; i < N; i++){
			cin >> mo;

			for(int j = 0; j + mo <= M; j++)
				d[j+mo] |= d[j];

		}

		int max = 0;
		for(int i = 0; i <= M; i++)
			if(d[i] && !so[i] && max < i)
				max = i;
		if(max)
			cout << max << endl;
		else
			cout << "NA" << endl;
	}
	

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
bool e[1000001],dp[1000010];
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+3;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>
#include <cstring>
using namespace std;

#define MAXNUM 1000001

bool prime[MAXNUM];

void eratosthenes()
{
	prime[0]=prime[1]=false;

	for(int i=2; i<MAXNUM; i++)
	{
		prime[i]=true;
	}
	
	for(int i=2; i*i<MAXNUM; i++)
	{
		if(prime[i])
		{
			for(int j=i*i; j<MAXNUM; j+=i)
			{
				prime[j]=false;
			}
		}
	}
}


bool dp[1000001];

int main()
{
	eratosthenes();
	int N,B,c[30];
	while(cin >> N >> B)
	{
		memset(dp,0,sizeof(dp));
		for(int i=0; i<N; i++)
			cin >> c[i];
			
		dp[0]=1;
		
		for(int i=0; i<N; i++)
		for(int j=0; j<B; j++)
		{
			if(j+c[i]>B) break;
			if(dp[j]) dp[j+c[i]]=1;
		}
		
		bool g=false;;
		for(int i=B; i>0; i--)
		{
			if(dp[i]&&prime[i])
			{
				g=true;
				cout << i << endl;
				break;
			}
		}
		if(!g) cout << "NA" << endl;
	}
}

C++: #include<iostream>

bool prime[1000001], dp[1000001];

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

	int n, x, a[30];
	while(std::cin >> n >> x, n){
		for(int i=0;i<=x;i++){
			dp[i] = false;
		}

		for(int i=0;i<n;i++){
			std::cin >> a[i];
		}

		int res = 0;

		dp[0] = true;
		for(int i=1;i<=x;i++){
			for(int j=0;j<n;j++){
				if(i-a[j] >= 0 && dp[i-a[j]]){
					dp[i] = true;
					break;
				}
			}
			if(dp[i] && prime[i]){
				res = i;
			}
		}

		if(res != 0){
			std::cout << res << std::endl;
		}else{
			std::cout << "NA" << std::endl;
		}
	}
}

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

bool prime[10000001];
bool dp[10000001];
int menu[30];
int n,x;

void make_prime()
{
  memset(prime,true,sizeof(prime));
  prime[0]=prime[1]=false;
  for(int i=2;i<10000001;i++)
    {
      if(prime[i])
	{
	  for(int j=i+i;j<10000001;j+=i)
	    prime[j]=false;
	}
    }
}

int main()
{
  make_prime();
  for(;cin>>n>>x,n;)
    {
      memset(dp,false,sizeof(dp));
      for(int i=0;i<n;i++)
	{
	  cin>>menu[i];
	  dp[menu[i]]=true;	  
	}
      int ans=-1;
      for(int i=0;i<=x;i++)
	{
	  if(dp[i])
	    for(int j=0;j<n;j++)
	      if(i+menu[j]<=x)
		dp[i+menu[j]]=true;	  
	}
      for(int i=x;i>0;i--)
	if(prime[i]&&dp[i])
	  {
	    ans=i;
	    break;
	  }
      if(ans!=-1)
	cout<<ans<<endl;
      else
	cout<<"NA"<<endl;
    }
}