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>
using namespace std;

bool is_prime[1000000+1];
void prime(int n){
	for(int i=0;i<n+1;i++){
		is_prime[i] = true;
	}
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<n+1;i++){
		if(is_prime[i]==true){
			for(int j=i+i;j<n+1;j+=i){
				is_prime[j] = false;
			}
		}
	}
}

int main()
{
	int n,m;
	prime(1000000);
	while(cin >> n >> m){
		if(!n && !m)
			break;
		bool DP[1000000+1];
		for(int i=0;i<m+1;i++)
			DP[i] = false;
		DP[0] = true;
		int ryori;
		for(int i=0;i<n;i++){
			cin >> ryori;
			for(int j=0;j<m+1-ryori;j++)
				if(DP[j])
					DP[j+ryori] = true;
		}		
		
		for(int i=m;i>=0;i--){
			if(is_prime[i] && DP[i]){
				cout << i << endl;
				break;
			}
			else if(i==0){
				cout << "NA" << endl;
				break;
			}
		}
	}
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

/*素数判定*/
const int MAX = 1000100;
bool prime[MAX];

void sieve(){
	fill(prime, prime+MAX, true);
	prime[0] = prime[1] = false;

	for(int i=0; i < MAX; i++){
		if(!prime[i]) continue;
		for(int j=i+i; j < MAX; j += i){
			prime[j] = false;
		}
	}
}

int main(){
	int n, x;
	sieve();

	while(cin >> n >> x, n+x){
		bool b[1000100] = {false};
		vector<int> v(n);
		rep(i, n) cin >> v[i];

		b[0] = true;
		rep(i, n){
			for(int j=0; j <= x; j++){
				if(b[j] && v[i]+j <= x) b[v[i]+j] = true;
			}
		}
		int ret = -1;
		for(int i=0; i <= x; i++) if(b[i] && prime[i]) ret = i;
		if(ret == -1) cout << "NA" << endl;
		else cout << ret << 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_back();
    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++: #define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

bool prime[1000001];
int dp[1000001];

int main(){

	fill((bool*)prime,(bool*)prime+1000000,true);

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

	int n,x;
	while(~scanf("%d %d",&n,&x)){
		if(n==x && x==0) break;

		memset(dp,0,sizeof(dp));
		vector<int> foods;
		for(int i=0;i<n;i++){
			int cost;
			scanf("%d",&cost);
			foods.push_back(cost);
			dp[cost] = 1;
		}

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

		for(int i=0;i<=x;i++){
			for(int j=0;j<foods.size();j++){
				if(i - foods[j] >= 0 && dp[i - foods[j]]){
					dp[i] = 1;
					break;
				}
			}
		}

		int res = -1;
		for(int i=x;i>=1;i--){
			if(!prime[i]) continue;
			

			if(dp[i]){
				res = i;
				goto found;
			}
		}
found:;
		if(res==-1) printf("NA\n");
		else printf("%d\n",res);
	}
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, a, n) for(int i = a;i < n;i++)
using namespace std;


int n, x;
int m[40];
int dp[40][1000010];
vector<int> prime;


void sieve(){
	rep(i, 0, x+1)
		if(1 < dp[n][i] && dp[n][i] <= x+1)prime.push_back(dp[n][i]);
	for(int i = 2;i*i <= x;i++){
		prime.erase(remove_if(prime.begin(), prime.end(), [&](int v){ return (v % i == 0); }), prime.end());
	}
	sort(prime.begin(), prime.end());
}


void makeDP(){
	rep(i, 1, n+1){
		rep(j, 0, x+1){
			if(j - m[i] >= 0) dp[i][j] = max(dp[i-1][j], dp[i][j - m[i]] + m[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
}


int main(){
	while(cin >> n >> x, n || x){
		rep(i, 1, n+1) cin >> m[i];

		makeDP();

		sieve();

		if(prime.size()) cout << prime.back() << endl;
		else cout << "NA" << endl;

		prime.clear();
	}

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
using namespace std;


int n, x;
int m[40];
int dp[1000010];
int p[1000000];


void sieve(){
	memset(p, 1, sizeof p);
	p[0] = p[1] = 0;
	for(int i = 2;i*i <= 1000000;i++){
		if(p[i]){
			for(int j = 2;i*j <= 1000000;j++)
				p[i*j] = 0;
		}
	}
}


void makeDP(){
	memset(dp, 0, sizeof dp);
	rep(i, 1, n+1){
		rep(j, 0, x+1){
			if(j >= m[i]) dp[j] = max(dp[j], dp[j-m[i]] + m[i]);
		}
	}
}


int main(){
	sieve();

	while(cin >> n >> x, n || x){
		rep(i, 1, n+1) cin >> m[i];

		makeDP();
		
		int ans = -1;
		repr(i, x, -1){
			if(p[dp[i]]){
				ans = dp[i];
				break;
			}
		}

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

	return 0;
}