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 <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;
const int L = 1000010;

int N, X;
bool p[L];

void init(){
  REP(i, L) p[i] = 1;
  p[0] = p[1] = 0;
  for(int i = 2; i <= sqrt(L); ++i){
    if(!p[i]) continue;
    for(int j = i + i; j < L; j += i) p[j] = 0;
  }
}

int solve(vector<int> &v){
  for(int i = X; i >= 0; --i) if(p[i] && v[i]) return i;
  return -1;
}

int main() {
  init();
  while(cin >>N >>X && N && X){
    vector<int> num(N), v(L, 0);
    v[0] = 1;
    REP(i, N){
      cin >>num[i];
      for(int j = num[i]; j < L; j++) if(v[j - num[i]]) v[j] = 1;
    }
    int res = solve(v);
    if(res == -1) cout <<"NA" <<endl;
    else cout <<res <<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <stack>
#include <list>

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,b,n) for(int i=b;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

bool dp[1000001], sosu[1000001];
int n, x;
int v[30];

void sosuu() {
  sosu[0]=false;
  for(int i=2; i*i<=x; i++) {
    if (sosu[i]) {
      for (int j=2*i; j<=x; j+=i) {
        sosu[j] = false;
      }
    }
  }
}
  

int main() {
  while(cin >> n >> x, n) {
    rep(i, n)
      cin >> v[i];
    rep(i, x+1) {
      sosu[i] = true;
      dp[i] = false;
    }
    sosuu();
    rep(i, n) {
      dp[v[i]]=true;
      for(int j=v[i]; j<=x; j++)
        if(dp[j] && j+v[i] <= x)
          dp[j+v[i]] = true;
    }
    while(x>0) {
      if(dp[x] && sosu[x])
        break;
      x--;
    }
    if(x==0)
      cout << "NA" << endl;
    else
      cout << x << endl;
  }

  return 0;
}

C++: #include<iostream>

#define MAX 1000001

bool isPrime[MAX];

void init(){
	for (int i = 2; i < MAX; i++)isPrime[i] = true;

	for (int i = 2; i*i < MAX; i++){
		if (isPrime[i]){
			for (int j = i * 2; j < MAX; j += i)isPrime[j] = false;
		}
	}
	return;
}

int main(){

	init();

	int n, x;
	while (std::cin >> n >> x, n || x){
		int price[31];
		bool isMake[MAX];

		for (int i = 0; i <= x; i++)isMake[i] = false;
		for (int i = 0; i < n; i++){
			std::cin >> price[i];
			isMake[price[i]] = true;
		}

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

		for (int i = x; i >= 0; i--){
			if (isMake[i] && isPrime[i]){
				std::cout << i << std::endl;
				break;
			}
			if (i == 0)std::cout << "NA" << std::endl;
		}
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define pb push_back
#define MAX 100005
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

bool Is_Prime(int n){
  if(n==1) return false;
  for(int i=2;i*i<n;i++){
    if(n%i==0){
      return false;
    }
  }
  return true;
}

signed main(){
    int n,x;
    while(cin>>n>>x,n){
      vector<int> v(n);
      rep(i,n)cin>>v[i];
      vector<int> dp(x+1);
      dp[0]=1;
      rep(j,n){
        loop(i,1,x+1){
          if(i-v[j]>=0&&dp[i-v[j]]==1){
            dp[i]=1;
          }
        }
      }
      for(int i=x;i>0;i--){
        if(dp[i]==1&&Is_Prime(i)){
          cout<<i<<endl;
          goto at;
        }
      }
      cout<<"NA"<<endl;
      at: ;
    }

  return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
#define KMAX 30
#define VMAX 1000000
int main( void )
{
	vector <bool> prime(VMAX+1, false);
	for ( int i = 3; i <= VMAX; i += 2 )
	{
		prime[i] = true;
	}
	prime[2] = true;
	for ( int i = 3; i * i <= VMAX; i += 2 )
	{
		if ( prime[i] )
		{
			for ( int j = i + i; j <= VMAX; j += i )
				prime[j] = false;
		}
	}

	while ( 1 )
	{
		int n, x;
		cin >> n >> x;
		if ( n == 0 && x == 0 )
			break;

		vector <int> K( KMAX );
		for ( int i = 0; i < n; i++ )
			cin >> K[i];

		vector < vector <bool> > T( KMAX, vector <bool>(VMAX, false) );

		for ( int i = 0; i < n; i++ )
			T[i][0] = true;
		for ( int i = K[0]; i <= x; i += K[0] )
			T[0][i] = true;

		for ( int i = 1; i < n; i++ )
		{
			for ( int j = 1; j < K[i]; j++ )
			{
				T[i][j] = T[i-1][j];
			}

			for ( int j = K[i]; j <= x; j++ )
			{
				T[i][j] = ( T[i-1][j] || T[i][j-K[i]] );
			}
		}

		int kotae = -1;
		for ( int i = x; i >= 2; i-- )
		{
			if ( prime[i] && T[n-1][i] )
			{
				kotae = i;
				break;
			}
		}

		if ( kotae == -1 )
			cout << "NA" << endl;
		else
			cout << kotae << endl;

	}

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <fstream>
#include <sstream>
#include <cstring>
using namespace std;
typedef long long ll;

int n, x;
int ps[40];

bool isp[1000010];
void sieve(){
    const int N = 1000000;
    memset(isp, true, sizeof(isp));
    
    isp[0] = false;
    isp[1] = true;
    
    for(int p=2;p*p<=N;p++)if(isp[p]){
        for(int j=p*p;j<=N;j+=p)isp[j] = false;
    }
}

bool can[1000010];
void gen(){
    memset(can, false, sizeof(can));
    can[0] = true;
    
    for(int sum=0;sum<x;sum++){
        for(int i=0;i<n;i++){
            if(sum + ps[i] <= x){
                can[sum + ps[i]] |= can[sum];
            }
        }
    }
}


int main(){
    sieve();
    
    while(cin >> n >> x){
        if(n == 0 && x == 0)break;
        
        for(int i=0;i<n;i++)cin >> ps[i];
        gen();
    
        int res = -1;
        for(int sum=x;sum>=1;sum--)if(can[sum] && isp[sum]){
            res = sum;
            break;
        }
        
        if(res == -1){
            cout << "NA" << endl;
        } else {
            cout << res << endl;
        }
    }
    
    return 0;
}