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])
		if n == 0 && x == 0 {
			break
		}
		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 <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();
   }
   return 0;
}

void initialize(){
    memset(is_prime_number, true, MAX_X);
    is_prime_number[0] = false, is_prime_number[1] = false;
    for(int i = 2; i <= 1000; ++i){
        if(is_prime_number[i]){
            for(int j = i * 2; 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 <iostream>
#include <vector>
using namespace std;
 
#define MAX_P 1000000
 
int main(){
    bool prime[MAX_P];
    prime[0] = false;
    prime[1] = false;
    for( int i = 2; i < MAX_P; i++ ) prime[i] = true;
    for( int i = 2; i < MAX_P; i++ ){
        if( prime[i] ){
            for( int j = 2*i; j < MAX_P; j += i ){
                prime[j] = false;
            }
        }
    }
    int n, x;
    while( cin >> n >> x, n || x ){
        vector<bool> dp(x+1);
        for( int i = 0; i <= x; i++ ) dp[i] = false;
        vector<int> p(n);
        for( int i = 0; i < n; i++ ){
            cin >> p[i];
        }
        dp[0] = true;
        int max = 0;
        for( int i = 0; i <= x; i++ ){
            if( dp[i] ){
                if( prime[i] == true && max < i ) max = i;
                for( int j = 0; j < n; j++ ){
                    dp[i+p[j]] = true;
                }
            }
        }
        if( max > 0 ) cout << max << endl;
        else cout << "NA" << endl;
    }
}

C++: #include<iostream>
#include<algorithm>
#define INF 999999
typedef long long ll;
using namespace std;
int n,a,b,c,maxm,x;
int sum,miniNo,minim;
bool t[1000001];
bool isPrime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return false;
	}
	return true;
}
int main(){
	while(1){
		fill(t,t+1000001,0);
		cin>>n>>x;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>a;
			t[a]=true;
			for(int j=2;j+a<1000001;j++){
				t[j+a]=(t[j]||t[j+a]);
			}
		}
		b=0;
		for(int i=x;i>1;i--){
			if(isPrime(i)&&t[i]){
				cout<<i<<endl;
				b=1;
				break;
			}
		}
		if(b==0)cout<<"NA"<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int n, x;

	while( true ) {
		cin >> n >> x;

		if(n == 0 && x == 0) {
			break;
		}

		vector< int > num(n);

		for(int i = 0; i < n; i++) {
			cin >> num[i];
		}

		vector< vector< int > > ans(n + 1, vector< int >(x + 1, 0));

		for(int i = 0; i < n - 1; i++) {
			for(int j = 0; j <= x; j++) {
				if(j < num[i]) {
					ans[i + 1][j] = ans[i][j];
				} else {
					ans[i + 1][j] = max(ans[i][j], ans[i + 1][j - num[i]] + num[i]);
				}
			}
		}

		vector< int > p(x + 1, 1);
		p[1] = 0;

		for(int i = 1; i * i <= x; i++) {
			if(p[i] == 1) {
				for(int j = 2; i * j <= x; j++) {
					p[i * j] = 0;
				}
			}
		}

		int money = 0;
		for(int i = 0; i <= n; i++) {
			for(int j = 0; j <= x; j++) {
				if(p[ans[i][j]] == 1) {
					money = max(money, ans[i][j]);
				}
			}
		}
		if(money != 0) {
			cout << money << endl;
		} else {
			cout << "NA" << endl;
		}
	}
}

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

using namespace std;

bool prime[1000001],dp[1000001];

void make_prime(){
  for(int i=0;i<1000001;i++) prime[i]=true;
  prime[0]=prime[1]=false;
  for(int i=2;i<=1000000;i++){
    if(prime[i]){
      for(int j=i*2;j<1000001;j+=i){
          prime[j]=false;
        }
    }
  }
}

int n,x;
vector<int> price;

int main(){
  make_prime();

  while(1){
    cin>>n>>x;
    if(!n && !x)break;
    while(price.size())price.pop();
    for(int i=0;i<1000001;i++){
      dp[i]=false;
    }
    for(int i=0;i<n;i++){
      int tmp;
      cin>>tmp;
      price.push_back(tmp);
      dp[tmp]=true;
    }

    sort(price.begin(),price.end());

    for(int i=0;i<n;i++){
      for(int j=0;j+price[i]<=x;j++){
        if(dp[j]) dp[j+price[i]]=true;
      }
    }

    int ans=0;

    for(int i=x;i>=1;i--){
      if(dp[i] && prime[i]){
        ans=i; break;
      }
    }

    if(ans==0){
      cout<<"NA"<<endl;
    }else{
      cout<<ans<<endl;
    }
  }
  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] && prime[i]) {
				printf("%d\n", i); flag = true; break;
			}
		}
		if(!flag) printf("NA\n");
	}
}

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

int main()
{
    int n, m;
    while(cin >> n >> m && (n || m)) {
        int cnt=0;vector<int> primes; bool num[m];
        memset(num, false, sizeof(num));
        num[0] = true;

        for(int i=0;i < n;++i) {int hoge; cin>>hoge; if(!(hoge%2)){++cnt;}}
        if (cnt == n) {puts("NA"); continue;}

        for(int i=2,len=m/2;i<=len;++i) {
            if (num[i-1]) continue;
            for(int j=i+i;j <= m;j+=i) {
                num[j-1] = true;
            }
        }

        for(int i=0;i < m;++i) {
            if (!num[i]) {
                primes.push_back(i+1);
            }
        }

        cout << primes.back() << endl;
    }

    return 0;
}