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>

bool prime[1000001], dp[1000001];

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

	int n, x, a[30];
	while(std::cin >> n >> x, n){
		for(int i=0;i<=x;i++){
			dp[i] = false;
		}

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

		int res = 0;

		dp[0] = true;
		for(int i=1;i<=x;i++){
			for(int j=0;j<n;j++){
				if(i-a[j] >= 0 && dp[i-a[j]]){
					dp[i] = true;
					break;
				}
			}
			if(dp[i] && prime[i]){
				res = i;
			}
		}

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

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

int p[1000001];
int dp[1000001];
int main(){
	int n,x;
	while(cin >> n >> x && n){
		for(int i = 0 ; i < 1000001 ; i++) p[i] = 1 , dp[i] = 0;
		p[0] = p[1] = 0;
		for(int i = 1 ; i*i <= 1000000 ; i++){
			if( p[i] ){
				for(int j = i * i ; j <= 1000000 ; j+=i){
					p[j] = 0;
				}
			}
		}
		dp[0] = 1;
		for(int i = 0 ; i < n ; i++){
			int t;
			cin >> t;
			for(int j = t ; j < 1000001 ; j++){
				dp[j] |= dp[j-t];
			}
		}
		while(x>0 && (p[x] == 0 || dp[x] == 0) ){
			x--;
		}
		if( x == 0 ){
			cout << "NA" << endl;
		}else{
			cout << x << endl;
		}
	}
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int XMAX = 1000000;
constexpr int SQRTXMAX = (int)sqrt(XMAX);

bool is_prime[XMAX + 1];
bool dp[XMAX + 1];
int cost[30];

int main() {
  // prime
  memset(is_prime, true, sizeof(is_prime));
  is_prime[0] = is_prime[1] = false
  for (int i = 2; i <= SQRTXMAX) {
    if (is_prime[i]) {
      int current = i * i;
      for (int j = i * i; j <= XMAX; j += i) {
        is_prime[j] = false;
      }
    }
  }

  int n, x;
  while (cin >> n >> x, n) {
    for (int i = 0; i < n; i++) cin >> cost[i];

    // dp
    r = 0;
    dp[0] = true;
    for (int i = 1; i <= x; i++) {
      for (int j = 0; j < n; j++) {
        int k = i - cost[j];
        if (k >= 0 && dp[k]) {
          dp[i] = true;
          if (is_prime[i]) r = i;
          break;
        }
      }
    }

    if (r == 0) {
      cout << "NA" << endl;
    } else {
      cout << r << endl;
    }
  }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
bool dp[1000001]={true},prime[1000001]={true,true};
int solve(int &i){
  while(i--) if(dp[i] && !prime[i]) return i;
}
int main(){
  int n,x,data[30],ans;
  for(int i = 2 ; i * i < 1000001 ; i++ ){
    if(!prime[i]) for(int j = 2 ; i * j < 1000001 ; j++ ) prime[i*j] = true;
  }
  while(cin >> n >> x , n){
    for(int i = 1 ; i <= x ; i++ ) dp[i] = false;
    for(int i = 0 ; i < n ; i++ ) cin >> data[i];
    for(int i = 0 ; i <= x ; i++ ){
      if(dp[i]) for(int j = 0 ; j < n ; j++ )
        if(i+data[j] <= x) dp[i+data[j]] = true;
    }
    if(ans = solve(x)) cout << ans << endl;
    else cout << "NA" << endl;
  }
}

C++: #include <iostream>
#include <string.h>
#include <set>
using namespace std;

const int LIMIT = 1000000;

int main()
{
	bool prime[ LIMIT + 1 ];
	memset( prime, false, sizeof(prime) );
	prime[ 0 ] = prime[ 1 ] = true;
	for( int i = 2; i < LIMIT + 1; ++i ){
		if( prime[ i ] ) continue;
		for( int j = i + i; j < LIMIT + 1; 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;
			if( p <= LIMIT ){
				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 <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;
}