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 <algorithm>
#include <cmath>
using namespace std;

const int N = 1000000;
int dp[N + 1], primes[N + 1];
int main(){
    fill(primes, primes + N + 1, 1);
    primes[0] = primes[1] = 0;
    for(int i = 2;i <= sqrt(N);++i){
        if(primes[i]){
            for(int j = i + i;j <= N;j += i){
                primes[j] = 0;
            }
        }
    }
    int n, x, a, ans;
    int ps[30];
    while(cin >> n >> x, n && x){
        fill(dp, dp + N + 1, 0);
        ans = 0;
        for(int i = 0;i < n;++i){
            cin >> a;
            ps[i] = a;
            dp[a] = 1;
        }
        for(int i = 0;i <= x;++i){
            if(dp[i]){
                for(int j = 0;j < n;++j){
                    if(i + ps[j] <= N && !dp[i + ps[j]]){
                        dp[i + ps[j]] = 1;
                    }
                }
            }
        }
        for(int i = x;i > 0;--i){
            if(dp[i] && primes[i]){
                ans = i;
                break;
            }
        }
        if(ans) cout << ans << endl;
        else cout << "NA" << endl;
    }
}

C++: #include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

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

const int INF = 1001001001;
const int MAX = 1000000;

int main()
{
	bool isprime[MAX + 1];
	fill(isprime, isprime+MAX+1, true);
	isprime[0] = isprime[1] = false;
	reps(i, 2, MAX){
		if(isprime[i]){
			for(int j=i*2; j<=MAX; j+=i)
				isprime[j] = false;
		}
	}

	int n;
	while(scanf("%d", &n), n){
		int x;
		scanf("%d", &x);

		int p[30];
		rep(i, n)
			scanf("%d", &p[i]);

		int ans = -1;
		bool dp[1000001] = {false};
		dp[0] = true;
		reps(i, 1, x+1){
			rep(j, n)
				dp[i] |= i>=p[j] && dp[i-p[j]];
			if(dp[i] && isprime[i])
				ans = i;
		}

		if(ans == -1)
			puts("NA");
		else
			printf("%d\n", ans);
	}

	return 0;
}

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

bool prime[2000000];
bool dp[2000000];

int main()
{
	int n, x;
	
	prime[0] = true;
	for (int i = 2; i < 2000000; i++){
		prime[i] = true;
	}
	
	for (int i = 2; i * i < 2000000; i++){
		for (int j = i * i; j < 2000000; j += i){
			prime[j] = false;
		}
	}
	
	while (scanf("%d %d", &n, &x), n + x){
		memset(dp, 0, sizeof(dp));
		dp[0] = true;
		
		for (int i = 0; i < n; i++){
			int yen;
			scanf("%d", &yen);
			for (int i = 0; i <= 1000000; i++){
				if (dp[i]){
					dp[i + yen] = true;
				}
			}
		}
		
		for (int i = x; i >= 0; i--){
			if (dp[i] && prime[i]){
				if (i == 0){
					printf("NA\n");
				}
				else {
					printf("%d\n", i);
				}
				break;
			}
		}
	}
	
	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 x,cnt,cnt2,food;
	int n,d=0,g,kakaku[31],youso[1000001]={0};
	scanf("%d %d",&n,&lx);
	while(n!=0&&x!=0){
		for(cnt=1;cnt<=n;cnt++){
			scanf("%ld",&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,&lx);
	}
	return 0;
}

C++: #include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<vector>
using namespace std;

#define M 1000001

int main() {
	static char gosei[M] = {};

	//????????°???1???
	for (int i = 2; i <= sqrt(M); i++)
		if (gosei[i] == 0) {
			for (int j = 2, k = 0; (k = i*j) <= M; j++)
				gosei[k] = 1;
		}

	static char dp[M];
	for (int n, x; cin >> n >> x&&n&&x;) {
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;

		for (int i = 0; i < n; i++) {
			int b; cin >> b;
			for (int j = 0; j + b <= x; j++)
				if (dp[j]) dp[j + b] = 1;
		}

		bool NA = true;
		for (int i = x; i >= 1; i--) {
			if (dp[i] && !gosei[i]) {
				cout << i << endl;
				NA = false;
				break;
			}
		}
		if (NA)cout << "NA" << endl;
	}
	return 0;
}

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

using namespace std;

vector<int> price;
list<int> primes;

const int M = 1000000;
const int L = 30;
const int D = 1;
const int S = M/D;
pair<int,int> memo[S][L];

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)
{
	pair<int,int>& pa = memo[x%S][pos];
	if( pa.first == x && -1 < pa.second )
		return pa.second;

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

	pa.first = x;
	pa.second = result;
	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 < S; i++ ) {
			for( int j = 0; j < L; j++ ) {			
				memo[i][j] = make_pair(-1,-1);
			}
		}

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

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}