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 <math.h>

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 < sqrt(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 && 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 <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9


int main(){
    int N = 1e6+1;
    vector<bool> isPrime(N, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i < N; i++) {
        if (!isPrime[i]) continue;
        for (int j = i*i; j < N; j += i) isPrime[j] = false;
    }

    while(true){
        int n,x;
        cin >> n >> x ;
        if(n == 0 && x == 0){
            break;
        }

        vector<int> dishes(n,0);

        FOR(i,0,n){
            cin >> dishes[i];
        }
        vector<bool> dp(x+1,false);
        dp[0] = true;

        int ans = 0;
        for(auto dish:dishes){
            FOR(i,0,x+1){
                if((i+dish < x+1) && dp[i]){
                    if(isPrime[i+dish])
                       ans = max(ans,i + dish);
                    dp[i+dish] = true;
                }
            }
        }

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

C++: #include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define MP 10000001
using namespace std;
bool p[MP]; int n,x,c[30],ans;
bool rec(int a,int s){
	int f=0;
	for(int i=s;i<n&&a>=c[i];i++){
		if(a==c[i])return 1;
		else f=rec(a-c[i],i);
		if(f) return 1;
	}
	return f;
}
int main(){
	for(int i=2;i*i<MP;i++)if(!p[i])for(int j=i+i;j<MP;j+=i)p[j]=1;
	p[0]=p[1]=1;
	while(cin>>n>>x,n){
		rep(i,n)cin>>c[i]; sort(c,c+n);
		for(ans=x;ans>=c[0];ans--)if(!p[ans]&&rec(ans,0))break;
		if(ans<c[0])cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

C++: #include<stdio.h>
#include<string.h>
#include<iostream>
int hideo[1000001] = { 0 };
int noyori = 0, debu = 0, n, x, temp = 1, ruio[31] = { 0 };
int main(void)
{
	while (scanf("%d %d", &n, &x)) {
		if (n == 0 && x == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ruio[i]);
			hideo[ruio[i]] = 1;
		}
		while (temp != x) {
			if (hideo[temp] == 1) {
				for (int j = 1; j <= n; j++) {
					if (temp + ruio[j] > x)continue;
					if (hideo[temp + ruio[j]] == 0) {
						hideo[temp + ruio[j]] = 1;
					}
				}
			}
			temp++;
		}
		for (int i = x; i >= 1; i--) {
			if (hideo[i] == 1) {
				for (int j = 2; j < i - 1; j++) {
					if (i%j == 0) {
						debu = 1;
					}
				}
				if (debu == 0) {
					noyori = i;
					break;
				}
			}
			debu = 0;
		}
		if (noyori > 1) {
			printf("%d\n", noyori);
		}
		else {
			printf("NA\n");
		}
		temp = 1;
		noyori = 0;
		debu = 0;
		for (int i = 0; i <= n; i++) {
			ruio[i] = 0;
		}
		for (int i = 1; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

C++: #include <stdio.h>
int n, x, a[30]; bool dp[1000001], prime[1000001];
int main() {
	for(int i = 2; i <= 1000000; i++) prime[i] = true;
	for(int i = 2; i <= 1000; i++) {
		if(!prime[i]) continue;
		for(int j = i * i; j <= 1000000; j += i) prime[j] = false;
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		for(int i = 0; i < x; i++) dp[i + 1] = false; dp[0] = true;
		for(int i = 1; i <= x; i++) {
			for(int j = 0; j < n; j++) {
				if(i - a[j] >= 0) dp[i] = dp[i] || dp[i - a[j]];
			}
		}
		bool flag = false;
		for(int i = x; i >= 1; i--) {
			if(dp[i]) {
				printf("%d\n", i); flag = true;
			}
		}
		if(!flag) printf("NA\n");
	}
}

C++: #include <iostream>
#include <vector>
#include <list>
#include <cmath>

using namespace std;

vector<int> price;
list<int> primes;
//int memo[1000000][30];

void mk_primes(int x)
{
	for( int i = 3; i <= x; i+=2 ) {
		for( int j = 3; j <= sqrt(i); j++ ) {
			if( i % j == 0 ) {
				goto NEXT;
			}
		}
		primes.push_front(i);
	NEXT:;		
	}
}

int solve(int x, int pos)
{
	// int& result = memo[x][pos];

	// if( -1 < result )
	// 	return result;

	int result = 0;

	int p = price[pos++];
	int s = x / p;

	if( price.size() == pos ) {

		if( s*p == x ) {
			result = 1;
			// cout << "(" << p << "*" << s << ")";
		}
		
		
	} else {

		for( int i = 0; i <= s; i++ ) {

			int t = i * p;
			result = solve(x-t, pos);
			if( result ) {
				// cout << "(" << p << "*" << i << ")";
				break;
			}
		}
	}

	return result;
}

int main(int argc, char* argv[])
{
	while(1) {

		int n; cin >> n;
		int x; cin >> x;

		if( n == 0 && x == 0)
			break;
	
		for( int i = 0; i < n; i++ ) {
			int p; cin >> p;
			price.push_back(p);
		}

		mk_primes(x);

		// for( int i = 0; i < 1000000; i++ ) {
		// 	for( int j = 0; j < 30; j++ ) {			
		// 		memo[i][j] = -1;
		// 	}
		// }

		for( auto p : primes ) {
			if( solve(p, 0) ) {
				cout << p << endl;
				goto LAST;
			}
		}

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int	flg[1000001],gen[1000001];
int main(void)
{
	int n,x,j,i,kazu[30],ff;
	
	for(i=2;i<=1000000;i++) flg[i]=1;
	for(i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
	while(1){
		scanf("%d %d",&n,&x);
		if(n==0 && x==0) break;
		for(i=0;i<n;i++) scanf("%d",&kazu[i]);
		for(i=0;i<=x;i++) gen[i]=0;
		gen[0]=1;
		for(i=0;i<n;i++){
			for(j=0;j<x;j++){
				if(gen[j]==1){
					if(j+kazu[i]<=x) gen[j+kazu[i]]=1;
				}
			}
		}
		ff=0;
		for(i=x;i>=2;i--){
			if(gen[i]==1 && flg[i]==1){
				ff=1;
				break;
			}
		}
		if(ff==0) printf("NA\n");
		else printf("%d\n",i);
	}
	return 0;
}