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<stdio.h>
#include <string.h>
int isPrime(int x){
	int i;
	if(x<2) return 0;
	else if(x==2) return 1;
	if(x%2==0) return 0;
	for(i=3;i*i<=x;i+=2){
		if(x%i==0) return 0;
	}
	return 1;
}
int p,cnt,cnt2,food;
int n,d=0,g,kakaku[31],flag,youso[1000002]={0};
int main()
{
	scanf("%d %d",&n,&p);
	while(1){
		//memset(youso, 0, sizeof(youso));
		
		if(n==0&&p==0){
			break;
		}
		for(cnt=1;cnt<=n;cnt++){
			scanf("%d",&food);
			youso[food]=1;
			kakaku[cnt]=food;
		}
		for(cnt=0;cnt<=p;cnt++){
			if(youso[cnt]==1){
				for(cnt2=1;cnt2<=n;cnt2++){
					if(cnt+kakaku[cnt2]<=p){
						youso[cnt+kakaku[cnt2]]=1;
					}
				}
			}
		}
		flag=0;
		for(cnt=p;cnt>=0;cnt--){
			if(youso[cnt]==1){
				g=cnt;
				d=isPrime(g);
				if(d==1){
					flag=1;
					d=cnt;
					printf("%d\n",d);
					break;
				}
			}
		}
		if(flag==0){
			printf("NA\n");
		}
		d=0;
		flag=0;
		for(int i=0;i<p+1;i++){
			youso[i]=0;
		}
		scanf("%d %d",&n,&p);
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
	int n, x;
	vector<int> furui(1000000+1, 0);
	furui[0] = furui[1] = 1;
	for (int i = 2; i*i <= 1000000; i++) {
		if (furui[i] == 0) {
			for (int j = 2; i*j <= 1000000; j++) {
				furui[i*j] = 1;
			}
		}
	}
	while (cin >> n >> x) {
		if (n == 0 && x == 0) {
			break;
		}
		vector<int> en(n);
		vector<int> dp(x+1, 0);
		for (int i = 0; i < n; i++) {
			cin >> en[i];
			dp[en[i]] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= x; j++) {
				if (j < en[i]) {
				} else {
					dp[j] = max(dp[j], dp[j-en[i]]);
				}
			}
		}
		bool hantei = true;
		for (int i = x; i >= 0; i--) {
			if (dp[i] > 0 && furui[i] == 0) {
				cout << i << endl;
				hantei = false;
				break;
			}
		}
		if (hantei) {
			cout << "NA" << endl;
		}
	}
	return 0;
}

C++: #include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
bool prime[1000001];

void init(){
	memset(prime,1,1000001);
	prime[0] = prime[1] = false;
	for(int i=0;i*i<=1000000;i++){
		if(prime[i]){
			for(int j=i*i;j<1000001;j+=i)
				prime[j] = false;
		}
	}
}
int main(){
	int n,x;
	
	init();
	
	while(cin >> n >> x,x){
		queue<int> Q;
		vector<int> data(n);
		for(int i=0;i<n;i++){
			cin >> data[i];
		}
		bool able[1000001] ={0};
		Q.push(0);
		while(Q.size()){
			int q = Q.front();Q.pop();
			
			for(int i=0;i<n;i++){
				int next = q + data[i];
				if(next>1000000)continue;
				if(able[next])continue;
				Q.push(next);
				able[next] = true;
			}
		}
		for(int i=x;i>1;i--){
			if(able[i] && prime[i]){
				cout << i << endl;
				goto l;
			}
		}
		cout << "NA" << endl;
		l:;
	}
}

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

int main() {

	vector<int> prim(1000000+1);
	fill(prim.begin(),prim.end(),1);
	prim[0]=0;
	prim[1]=0;
	for(int i=2;i<prim.size();i++){
		if( prim[i]!=0 ){
			int x=i+i;
			while(x<prim.size()){
				prim[x]=0;
				x+=i;
			}
		}
	}

	while(true)
	{
		int N,X;
		cin >> N >> X;
		if(N==0 && X==0)break;
		
		vector<int> food;
		for(int i=0;i<N;i++){
			int m;
			cin >> m;
			food.push_back(m);
		}
		
		vector<int> num(X+1);
		fill(num.begin(),num.end(),0);
		for(int i=0;i<N;i++){
			if( food[i]<=X ){
				num[ food[i] ]=1;
			}
		}
		for(int i=0;i<=X;i++){
			if( num[i]!=0){
				for(int j=0;j<N;j++){
					if( i+food[j]<=X){
						num[i+food[j]]=1;
					}
				}
			}
		}
		int ans=-1;
		for(int x=X;x>=0;x--){
			if( prim[x]==1 && num[x]!=0){
				ans = x;
				break;
			}			
		}
		if(ans>0){
			cout << ans << endl;
		}else{
			cout << "NA" << endl;
		}
	}
	


	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <vector>
#include <cmath>

using namespace std;

vector<int> primes;

void make_primes( int lim ) {
  vector<bool> vs( lim + 1 );
  fill( vs.begin(), vs.end(), true );
  vs[ 0 ] = vs[ 1 ] = false;
  const int l = (int)sqrt( lim );
  for ( int i = 2; i <= l; i++ ){
	if ( vs[ i ] ) {
	  for ( int j = i * i; j <= lim; j += i ) {
		vs[ j ] = false;
	  }
	}
  }
  for ( int i = 2; i <= lim; i++ ) {
	if ( vs[ i ] ) {
	  primes.push_back( i );
	}
  }
}

bool isPrime( int n ) {
  return binary_search( primes.begin(), primes.end(), n );
}

int main() {
  make_primes( 1000000 );
  while( true ) {
	int n, x;
	cin >> n >> x;
	if ( n == 0 and x == 0 ) break;
	vector<int> vs( n );
	for ( int i = 0; i < n; i++ ) {
	  cin >> vs[ i ];
	}
	sort( vs.begin(), vs.end() );
	vector<int> cs;
	cs.push_back( 0 );
	vector<int> indices( n );
	fill( indices.begin(), indices.end(), 0 );
	while( cs.back() <= x ) {
	  int mv = 100000000;
	  int mi = -1;
	  for ( int i = 0; i < n; i++ ) {
		if ( mv > cs[ indices[ i ] ] + vs[ i ] ) {
		  mi = i;
		  mv = cs[ indices[ i ] ] + vs[ i ];
		}
	  }
	  if ( cs.back() < mv ) {
		cs.push_back( mv );
	  } 
	  indices[ mi ]++;
	}
	reverse( cs.begin(), cs.end() );
	bool s = false;
	for ( int v : cs ) {
	  if ( isPrime( v ) ) {
		s = true;
		cout << v << endl;
		break;
	  }
	}
	if ( not s ) {
	  cout << "NA" << endl;
	}
  }
}

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

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define MAX 1000100

int n,x;
int a[35],dp[MAX];
bool isprime[MAX];

void sieve(){
  int i,j;

  rep(i,MAX) isprime[i] = true;
  isprime[0] = isprime[1] = false;
  for(i = 2; i*i <= MAX; i++) if(isprime[i]){
    for(j = 2*i; j <= MAX; j += i) isprime[j] = false;
  }
}

int dfs(int depth, int v){ // how to pruning???
  int i;

  if(dp[v] != -1) return dp[v];
  if(depth == n){
    if(isprime[v]) return v; else return 0;
  }

  int K = ((x - v) / a[depth])+1, ret = 0;
  rep(i,K){
    int tmp = v + i * a[depth];
    ret = max(ret, max(dfs(depth+1, v), dfs(depth+1, tmp))); // constant multiple get or not get
  }

  return dp[v] = ret;
}

int main(){
  int i,j,k;

  sieve();

  for(;;){
    scanf("%d %d",&n,&x); if(n == 0 && x == 0) break;
    rep(i,n) scanf("%d",&a[i]);

    rep(i,MAX) dp[i] = -1;

    int res = dfs(0,0);
    if(res == 0) cout << "NA" << endl; else cout << res << endl;
/*
    rep(i,MAX) dp[i] = 0;

    int res = 0;
    rep(i,n) for(j = 0; j <= x; j++){
      if(!isprime[j]) continue;
      int K = ((x-j) / a[i]) + 1;
      rep(k,K) if(j - k*a[i] >= 0) if(dp[j] < dp[j-k*a[i]] + k*a[i]){
        dp[j] = dp[j-k*a[i]] + k*a[i];
        res = ;
      }
    }

    cout << res << endl;
    */
  }

  return 0;
}