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 <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

const int INF = 1<<30;
const int MAX = 1000000;
typedef long long ll;

int main()
{
	bool dp[MAX+1]; // dp[i]
	bool prime[MAX+1];
	int n, m;
	memset(prime, true, sizeof(prime));

	for(int i = 2; i < sqrt(MAX); i++)
	{
		if(prime[i] == false)
		{
			continue;
		}
		for(int j = i*2; j < MAX; j += i)
		{
			prime[j] = false;
		}
	}

	while(cin >> n >> m ,n)
	{

		for(int i = 0; i <= MAX; i++)
		{
			dp[i] = false;
		}
		dp[0] = true;

		for(int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			for(int t = 0; t <= m-x; t++)
			{
				if(dp[t])
				{
					dp[t+x] = true;
				}
			}
		}

		int res = -1;
		for(int i = m; i >= 2; --i)
		{
			if(dp[i] && prime[i])
			{
				res = i;
				break;
			}
		}
		if(res ==  -1)
		{
			cout << "NA" << endl;
		}
		else
		{
			cout << res << endl;
		}

	}
}

C++: #include <bits/stdc++.h>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;
const double PI = acos(-1.0);
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to;
    int cost;
};

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

bool isPrime[1000010];
bool dp[1000010];

void Eratostenes(int N)
{
    rep(i, 1e6 + 1) isPrime[i] = true;

    isPrime[0] = false;
    isPrime[1] = false;

    for(int i = 2; i <= sqrt(N); i++)
    {
        if(isPrime[i])
        {
            for(int j = i * 2; j <= N; j += i)
                isPrime[j] = false;
        }
    }   
}

int main()
{
    int N, X;
    Eratostenes(1000000);   

    while(cin >> N >> X && N)
    {
        vector<int> v(N);
        rep(i, N) cin >> v[i];
        rep(i, N + 1) dp[i] = false;

        dp[0] = true;

        rep(i, N)
        {
            rep(j, X + 1)
            {
                if(!dp[j]) continue;

                dp[j + v[i]] = true;
            }
        }

        int ans = 0;

        rep(i, X + 1)
        {
            if(dp[i] && isPrime[i])
                ans = max(ans, i);
        }

        cout << (ans == 0 ? "NA" : to_string(ans)) << endl;

    }

    return 0;
}

C++: #include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    const int MAX=1000000;
    vector<bool> pri(MAX+1,true);
    pri[0]=pri[1]=false;
    for(int i=2;i<=sqrt(MAX);i++){
        if(pri[i]){
            for(int j=i*i;j<=MAX;j+=i){
                pri[j]=false;
            }
        }
    }
    int N,X;
    for(;;){
        scanf("%d%d",&N,&X);
        if(N==0&&X==0) break;
        vector<bool> has(X+1,false);
        has[0]=true;
        int in;
        for(int i=0;i<N;i++){
            scanf("%d",&in);
            for(int j=0;j<=X;j++){
                if(has[j]&&(j+in<=X)) has[j+in]=true;
            }
        }
        int ret=-1;
        for(int i=X;i>=0;i--){
            if(pri[i]&&has[i]){
                ret=i;
                break;
            }
        }
        if(ret==-1) printf("NA\n");
        else printf("%d\n",ret);
    }
}

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

int main(){
	int n,m,x,item;
	vector<bool> prime(1000001,true);
	prime[0]=prime[1]=false;
	/*ツづ督づゥツつ「*/
	for(int i=2;i<=1000;i++)if(prime[i])for(int j=i+i;j<=1000000;j+=i)prime[j]=0;
	
	while(cin >> n >> x && n && x){
		vector<bool> able(x+1,false);
		able[0]=true;
		
		for(int i=0;i<n;i++){
			cin >> item;
			for(int j=0;j+item<=x;j++){
				able[j+item] = able[j+item] | able[j];
			}
		}
		for(int i=x;i>=0;i--){
			if(able[i] && prime[i]){
				cout << i << endl;
				break;
			}
			if(!i)cout << "NA" << endl;
		}
	}
}

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

int main() {

	vector<int> prim(1000000+1);
	fill(prim.begin(),prim.end(),1);
	prim[0]=0;
	prim[1]=0;
	for(int i=2;i<prim.size();i++){
		if( prim[i]!=0 ){
			int x=i+i;
			while(x<prim.size()){
				prim[x]=0;
				x+=i;
			}
		}
	}

	while(true)
	{
		int N,X;
		cin >> N >> X;
		if(N==0 && X==0)break;
		
		vector<int> food;
		for(int i=0;i<N;i++){
			int m;
			cin >> m;
			food.push_back(m);
		}
		
		vector<int> num(X+1);
		fill(num.begin(),num.end(),0);
		for(int i=0;i<N;i++){
			if( food[i]<=X ){
				num[ food[i] ]=1;
			}
		}
		for(int i=0;i<=X;i++){
			if( num[i]!=0){
				for(int j=0;j<N;j++){
					if( i+food[j]<=X){
						num[i+food[j]]=1;
					}
				}
			}
		}
		int ans=-1;
		for(int x=X;x>=0;x--){
			if( prim[x]==1 && num[x]!=0){
				ans = x;
				break;
			}			
		}
		if(ans>0){
			cout << ans << endl;
		}else{
			cout << "NA" << endl;
		}
	}
	


	return 0;
}

C++: #include<stdio.h>
int isPrime(int x){
	int i;
	if(x<2) return 0;
	else if(x==2) return 1;
	if(x%2==0) return 0;
	for(i=3;i*i<=x;i+=2){
		if(x%i==0) return 0;
	}
	return 1;
}
int main()
{
	long cnt,cnt2;
	int n,x,d=0,g,food,kakaku[1000],youso[201001]={0};
	int flag=0;
	scanf("%d %d",&n,&x);
	while(n!=0&&x!=0){
		for(cnt=1;cnt<=n;cnt++){
			scanf("%d",&food);
			youso[food]=1;
			kakaku[cnt]=food;
		}
		for(cnt=1;cnt<=x;cnt++){
			if(youso[cnt]==1){
				for(cnt2=1;cnt2<=n;cnt2++){
					youso[cnt+kakaku[cnt2]]=1;
					if(cnt+kakaku[cnt2]>x){
						break;
					}
				}
			}
		}
		for(cnt=x;cnt>0;cnt--){
			if(youso[cnt]==1){
				g=cnt;
				d=isPrime(g);
				if(d==1){
					d=cnt;
					flag=1;
					printf("%d\n",d);
					break;
				}
			}
		}
		if(flag==0){
			printf("NA\n");
		}
		flag=0;
		d=0;
		for(cnt=1;cnt<=x;cnt++){
			youso[cnt]=0;
		}
		scanf("%d %d",&n,&x);
	}
	return 0;
}

C++: #include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    const int MAX=1000000;
    vector<bool> pri(MAX+1,true);
    pri[0]=pri[1]=false;
    for(int i=2;i<=sqrt(MAX);i++){
        if(pri[i]){
            for(int j=i*i;j<=MAX;j+=i){
                pri[j]=false;
            }
        }
    }
    int N,X;
    for(;;){
        scanf("%d%d",&N,&X);
        if(N==0&&X==0) break;
        vector<bool> has(X+1,false);
        has[0]=true;
        int in;
        for(int i=0;i<N;i++){
            scanf("%d",&in);
            for(int j=0;j<=X;j++){
                if(has[j]&&(j+in<=X)) has[j+in]=true;
            }
        }
        int ret=-1;
        for(int i=X;i>=0;i--){
            if(pri[i]&&has[i]){
                ret=i;
                break;
            }
        }
        if(ret==-1) printf("NA\n");
        else printf("%d\n",ret);
    }
}