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 <string.h>
#include <set>
using namespace std;

int main()
{
	bool prime[ 1000001 ];
	memset( prime, false, sizeof(prime) );
	prime[ 0 ] = prime[ 1 ] = true;
	for( int i = 2; i < 1000001; ++i ){
		if( prime[ i ] ) continue;
		for( int j = i + i; j < 1000001; j += i ){
			prime[ j ] = true;
		}
	}

	int n, x;
	while( cin >> n >> x && ( n || x ) ){
		bool* price = new bool[ x + 1 ]();
		set< int > menu;
		for( int i = 0; i < n; ++i ){
			int p;
			cin >> p;
			menu.insert( p );
			price[ p ] = true;
		}
		int ans = 0;
		for( int i = 0; i <= x; ++i ){
			if( !price[ i ] ) continue;
			if( !prime[ i ] ){
				ans = i;
			}
			set< int >::iterator itr = menu.begin();
			while( itr != menu.end() ){
				int a = i + *itr;
				if( a <= x ){
					price[ a ] = true;
				}
				++itr;
			}
		}

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

		delete [] price;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

bool is_prime[1000001];
bool dp[1000001];
int a[31];
int main() {
	memset(is_prime, 1, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= 1000000; i++) {
		if (is_prime[i]) {
			for (int j = i * 2; j <= 1000000; j += i)is_prime[j] = false;
		}
	}
	int n, x;
	while (cin >> n >> x, n) {
		rep(i, n)scanf("%d", &a[i]);
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		rep(i, x + 1) {
			rep(j, n)
				if (dp[i] && i + a[j] <= x)dp[i + a[j]] = true;
		}
		bool flag = true;
		for (int i = x; i > 0; i--) {
			if (dp[i] && is_prime[i]) {
				printf("%d\n", i);
				flag = false;
				break;
			}
		}
		if (flag)printf("NA\n");
	}
}

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

constexpr int MAX_X = 1000001;
constexpr int MAX_N = 31;

int n, x, values[MAX_N];
bool is_prime_number[MAX_X] = {true};

void initialize();

void solve();

int main(){
    initialize();
    while(true){
        memset(values, 0, MAX_N);

        std::cin >> n >> x;
        
        if(n + x == 0) break;
        
        for(int i = 0; i < n; ++i)
            std::cin >> values[i];

        solve();
    }
}

void initialize(){
    for(int i = 0; i <= MAX_X; ++i)
        is_prime_number[i] = true;
    is_prime_number[0] = false, is_prime_number[1] = false;
    for(int i = 2; i * i <= MAX_X; ++i){
        if(is_prime_number[i]){
            for(int j = i + 1; j < MAX_X; ++j){
                if(j % i == 0)
                    is_prime_number[j] = false;
            }
        }
    }
}

void solve(){
    int ans = 0;
    int dp[MAX_X];
    memset(dp, 0, MAX_X);

    /*
    std::cout << "x : " << x << std::endl << "n : " << n << std::endl;
    for(int i = 0; i < (x > 1000 ? 1000 : x); ++i){
        std::cout << i << " dp : " << dp[i] << std::endl;
    }
    */

    for(int i = 1; i <= x; ++i){
        int res = 0;
        for(int j = 0; j < n; ++j){
            if(values[j] <= i){
                res = std::max(dp[i - values[j]] + values[j], res);
            }
        }
        dp[i] = std::max(dp[i], res);
        if(is_prime_number[dp[i]]){
            ans = std::max(dp[i], ans);
        }
    }

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

}

C++: #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define EQ(a,b) (abs((a)-(b))<EPS)
#define Max_N 1000010
bool prime[Max_N];
int menu[30];
bool dp[Max_N];
void eratos()
{
	fill(prime,prime+Max_N,true);
	prime[0]=false;
	prime[1]=false;
	for(int i=2;i*i<Max_N;i++)
	{
		if(prime[i])
		{
			for(int j=2*i;j<Max_N;j+=i)
			{
				prime[j]=false;
			}
		}
	}
	return;
}
int main()
{
	fill(dp,dp+Max_N,false);
	eratos();
	while(1)
	{
		int n,x;
		cin >> n >> x;
		if(n==0&&x==0)break;
		for(int i=0;i<n;i++)
		{
			cin >> menu[i];
		}
		dp[0]=true;
		int ans=0;
		for(int i=1;i<=x;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i-menu[j]>=0&&dp[i-menu[j]])
				{
					dp[i]=true;
				}
			}
			if(prime[i]&&dp[i])
			{
				ans=i;
			}	
		}
		if(ans!=0)
		{
			cout << ans << endl;
		}
		else
		{
			cout << "NA" << endl;
		}
	}
	return 0;
}

C++: #include <cstdio>
#include <cstring>

using namespace std;

bool prime(int x)
{
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0) return (false);
	return (x != 1);
}

int main()
{
	int n, x;
	static bool dp[1000001];
	
	while (scanf("%d %d", &n, &x) && n){
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for (int i = 0; i < n; i++){
			int y;
			scanf("%d", &y);
			for (int r = 0; r + y <= x; r++){
				if (dp[r]) dp[r + y] = true;
			}
		}
		
		bool ng = true;
		for (int i = x; i >= 2; i--){
			if (dp[i] && prime(i)){
				printf("%d\n", i);
				ng = false;
				break;
			}
		}
		if (ng) printf("NA\n");
	}
	return (0);
}

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

bool budget[1000001], prime[1000001];

void eratosthenes() {
    fill(prime, prime+1000001, true);
    prime[0] = prime[1] = false;
    for (int i = 3; i <= 1000; i++) {
        if (prime[i]) {
            for (int d = i * 2, j = i + d; j <= 1000000; j += d) {
                prime[j] = false;
            }
        }
    }
}

int main() {
    int n, x, price[30], i, j;

    eratosthenes();

    while ((cin >> n >> x) && n) {
        for (i = 0; i < n; i++) {
            cin >> price[i];
        }
        // sort(price, price+n);

        fill(budget, budget+x+1, false);
        budget[0] = true;
        for (i = 0; i <= x; i++) {
            if (budget[i]) {
                for (j = 0; j < n; j++) {
                    if (i + price[j] <= x) {
                        budget[i + price[j]] = true;
                    }
                }
            }
        }

        for (i = x - 1 + (x&1); i > 0; i -= 2) {
            if (prime[i] && budget[i]) break;
        }

        if (i > 0) {
            cout << i;
        }
        else {
            cout << "NA";
        }
        cout << endl;
    }
    return 0;
}