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<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;

const int kN = 1000005;

void primeNumber(bool prime[kN]){
    rep(i,kN) prime[i] = 1;
    prime[0] = prime[1] = 0;
    rep(i,kN){
        if(prime[i]){
            for(int j = i + i; j < kN; j+=i){
                prime[j] = 0;
            }
        }
    }
}

void primeOfCuisine(int n, int a[40], bool prime[kN]){
    prime[0] = 1;
    rep(i,n){
        rep(j,kN){
            if(prime[j] == 1){
                if(j + a[i] >= kN) continue;
                prime[j + a[i]] = 1;
            }
        }
    }
}

void outputAns(bool a[kN], bool b[kN], int x){
    for(int i = x; i >= 0; i--){
        if(a[i] == 1 && b[i] == 1){
            cout << i << endl;
            return;
        }
    }
    cout << "NA" << endl;
    return;
}

int main(){
    int n, x, a[40];
    while(cin >> n >> x, n||x){
        bool is_prime[kN] = {0};
        bool is_prime_of_cuisine[kN] = {0};
        rep(i,n) cin >> a[i];
        primeNumber(is_prime);
        primeOfCuisine(n, a, is_prime_of_cuisine);
        outputAns(is_prime, is_prime_of_cuisine, x);
    }
}

C++: #include<iostream>
#include<algorithm>
#include<cstring>
#define M 1000001
using namespace std;

int n, x;
int data[33];
int prim[M];
int flg[M];
int p;

void solve(int i){

  if(i == n || p > x) return;
  if(flg[p]) return;
  
  solve(i+1);

  p += data[i];
  solve(i);
  p -= data[i];

  p += data[i];
  solve(i+1);
  p -= data[i];

  flg[p] = 1;
}


  
int main(){

  prim[0] = prim[1] = 1;
  for(int i=2;i*i<M;i++)
    if(!prim[i]) for(int j=i+i;j<M;j+=i) prim[j] = 1;

  for( ; ; ){
    cin >> n >> x;

    if(!n && !x) break;
    
    for(int i=0;i<n;i++) cin >> data[i];

    memset(flg, 0, sizeof(flg));
    p = 0;
    
    solve(0);
  
    int ans = -1;
    for(int i=0;i<=x;i++)
      if(!prim[i] && flg[i]) ans = i;

    if(ans == -1) cout << "NA\n";
    else cout << ans << endl;
  }

  
}

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

constexpr int MAX_N = 31, MAX_C = 1000001;
int n, max;
int cost[MAX_N];
bool dp[MAX_C];
bool prime_num[MAX_C];

int main() {
	while (1) {
		std::cin >> n >> max;
		if (n + max == 0)
			break;
		std::memset(prime_num, false, sizeof(prime_num));
		std::memset(dp, false, sizeof(dp));
		for (int i = 0; i < n; ++i)
			std::cin >> cost[i];
		for (int i = 2; i * i <= max; ++i) {
			if (!prime_num[i]) {
				for (int j = 2; i*j <= max; ++j)
					prime_num[i*j] = true;
			}
		}
		int ans = 0;
		for (int i = 0; i < n; ++i)
			dp[cost[i]] = true;

		for (int i = 1; i <= max; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i + cost[j] <= max&&dp[i])
					dp[i + cost[j]] = true;
				else if(!d[i])
					goto a;
			}
		}
	a:;
		for (int i = max; i >= 0; --i) {
			if (dp[i] && !prime_num[i]) {
				ans = i; 
				break;
			}
		}
		if (!ans)
			std::cout << "NA" <<std::endl;
		else
			std::cout << ans << std::endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e6) + 5;

bool isPrime[MAX_N];

bool sieve(int n){
    fill(isPrime, isPrime+n+1, true);
    isPrime[0] = isPrime[1] = false;
    for(int i=2;i*i<=n;i++){
        if(isPrime[i]){
            for(int j=i*i;j<=n;j+=i){
                isPrime[j] = false;
            }
        }
    }
}

bool dp[35][MAX_N];

int main() {
    sieve(1e6);
    int n, x;
    while(cin >> n >> x, n){
        int v[30];
        for(int i=0;i<n;i++) cin >> v[i];
        for(int i=0;i<=n;i++) fill(dp[i], dp[i]+x+1, false);
        dp[0][0] = true;
        for(int i=0;i<n;i++){
            for(int j=0;j<=x;j++){
                dp[i+1][j] |= dp[i][j];
                if(j+v[i]<=x){
                    dp[i][j+v[i]] |= dp[i][j];
                }
            }
        }
        int ans = -1;
        for(int i=2;i<=x;i++){
            if(dp[n][i] && isPrime[i]) ans = i;
        }
        if(ans > 0){
            cout << ans << endl;
        }
        else{
            cout << "NA" << endl;
        }
    }
    return 0;
}

C++: #include <iostream>

using namespace std;
int n, x, m, prises[30];
bool flag[1000001];

int sosuu(int n) {
	if (n == 2) return 1;
	if (n < 2 || n % 2 == 0) return 0;
	for (int i = 3; i * i <= n; i += 2)
			if (n % i == 0) return 0;
	return 1;
}

void max(int p) {
	if (p >= 1000000) return; 
	if (flag[p]) return;
	flag[p] = 1;
	for (int i = 0; i < n; ++i) {
		int k = p + prises[i];
		if (k > x) continue;
		if (k > m && sosuu(k)) m = k;
		max(k);
	}
}

int main() {
	for (;;) {
		for (int i = 0; i <= 1000000; ++i) flag[i] = 0;
		m = 0;
		cin >> n >> x;
		if (n == 0 && x == 0) break;
		for (int i = 0; i < n; ++i)
			cin >> prises[i];

		max(0);

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

C++: #include<stdio.h>
#include<string.h>
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 && noyori>7) {
			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 = 0; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

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, (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>1; i--)
		{
			if(dp[i]&&prime[i])
			{
				g=true;
				cout << i << endl;
				break;
			}
		}
		if(!g) cout << "NA" << endl;
	}
}