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

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, x;
int a[100];

bool is_prime[1001000];
//int prime[1001000];

bool dp[1001000];

int main(){
	REP(i, 1001000)is_prime[i] = 1;
	is_prime[0] = 0;
	//prime[0] = 1;
	//int p = 1;
	for (int i = 2; i <= 1000000; i++){
		if (is_prime[i]){
			//prime[p++] = i;
			for (int j = 2 * i; j <= 1000000; j += i){
				is_prime[j] = 0;
			}
		}
	}
	//int co = 0;
	//for (int i = 0;; i++){
	//	if (prime[i] == 0)break;
	//	co++;
	//}
	//cout << co << endl;
	while (cin >> n >> x&&n + x){
		REP(i, 1001000)dp[i] = 0;
		REP(i, n)cin >> a[i];
		dp[0] = 1;
		REP(i, n){
			REP(j, x + 1){
				if (dp[j] == 1){
					dp[j + a[i]] = 1;
				}
			}
		}
		bool f = 1;
		for (int i = x; i > 0; i--){
			if (dp[i] && is_prime[i]){
				cout << i << endl;
				f = 0;
				break;
			}
		}
		if (f)cout << "NA" << endl;
	}
}

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){
        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 = -1;
    int dp[MAX_X];
    memset(dp, 0, x);

    for(int i = 1; i <= x; ++i){
        int res = -1;
        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 != -1){
        std::cout << ans << std::endl;
    }
    else{
        std::cout << "NA" << std::endl;
    }
}

C++: #include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>

using namespace std;

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

int sosu[1111111];
int dp[1211111];
int main(){
	
	sosu[0]=1;
	sosu[1]=1;
	
	for(int i=2;i<1111111;i++){
		if(sosu[i]==1)continue;
		for(int j=i+i;j<1111111;j+=i){
			sosu[j]=1;
		}
	}
	
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		rep(i,1111111)dp[i]=0;
		dp[0]=1;
		
		int item[33];
		rep(i,n){
			cin>>item[i];
		}
		
		int ans=-1;
		rep(i,m+1){
			if(dp[i]==0)continue;
			if(sosu[i]==0)ans=i;
			rep(j,n){
				dp[i+item[j]]=1;
			}
		}
		if(ans==-1){
			puts("NA");
		}else{
			printf("%d\n",ans);
		}
	}
}

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

bool is[1000001];
bool isprime[1000001];

int main() {

    isprime[0] = isprime[1] = true;
    for(int i=4; i<=1000000; i+=2) isprime[i] = true;
    for(int i=3; i*i<=1000000; i+=2)
        for(int j=2; i*j<=1000000; ++j)
            isprime[i*j] = true;

    int n,x,s;
    while(cin>>n>>x, n|x) {
        memset(is, false, sizeof(is));
        is[0] = true;
        for(int i=0; i<n; ++i) {
            cin>>s;
            for(int j=1000000; j>=0; --j) {
                if(is[j]) {
                    for(int k=1; j+s*k <= x; ++k)
                        is[j+s*k] = true;
                }
            }
        }

        for(int j=x; j>=0; --j) {
            if(is[j] && !isprime[j]) {
                cout<<j<<endl;
                goto NEXT;
            }
        }
        cout<<"NA"<<endl;
    NEXT:;
    }
}

C++: #include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000000];
int m[1000000];

int isPrime(int x){
	if (x < 2)return 0;
	else if (x == 2) return 1;
	if (x % 2 == 0) return 0;
	for (int i = 3; i*i <= x; i += 2){
		if (x%i == 0) return 0;
	}
	return 1;
}


int main(){
	int n; int x;
	while (cin >> n >> x, n, x){
		memset(a, 0, sizeof(a));
		memset(m, 0, sizeof(m));
		for (int i = 0; i < n; i++){
			cin >> a[i];
			m[a[i]] = 1;
		}
		for (int i = 0; i <= x; i++){
			if (m[i] > 0){
				for (int j = 0; j < n; j++){
					m[i + a[j]] = 1;
				}
			}
		}
		bool flag = false;
		for (int i = x; i >= 0; i--){
			if (m[i] > 0) {
				if (isPrime(i) == 1) {
					cout << i << endl;
					flag = true;
					break;
				}
			}
		}
		if (flag == false){
			cout << "NA" << endl;
		}
	}
	return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int n, x;
int a[100];

bool is_prime[1001000];

bool dp[1001000];

int main(){
	REP(i, 1001000)is_prime[i] = 1;
	is_prime[0] = 0;
	for (int i = 2; i <= 1000000; i++){
		if (is_prime[i]){
			for (int j = 2 * i; j <= 1000000; j += i){
				is_prime[j] = 0;
			}
		}
	}
	while (cin >> n >> x&&n + x){
		REP(i, 1001000)dp[i] = 0;
		REP(i, n)cin >> a[i];
		dp[0] = 1;
		sort(a, a + n);
		REP(i, n){
			REP(j, x + 1){
				if (dp[j] == 1){
					dp[j + a[i]] = 1;
				}
			}
		}
		bool f = 1;
		for (int i = x; i > 0; i--){
			if (dp[i] && is_prime[i]){
				cout << i << endl;
				f = 0;
				break;
			}
		}
		if (f)cout << "NA" << endl;
	}
}