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<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=1;j+a<1000001;j++){
				t[j+a]=(t[j]||t[j+a]);
			}
		}
		b=0;
		for(int i=x-1;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 <list>
#include <map>
#include <cmath>

using namespace std;

vector<int> price;
list<int> primes;

const int M = 1000000;
const int L = 30;
const int D = 5;
const int S = M/D;
pair<int,int> memo[S][L];

void mk_primes(int x)
{
	for( int i = 3; i <= x; i+=2 ) {
		for( int j = 3; j <= sqrt(i); j++ ) {
			if( i % j == 0 ) {
				goto NEXT;
			}
		}
		primes.push_front(i);
	NEXT:;		
	}
}

int solve(int x, int pos)
{
	pair<int,int>& pa = memo[x%S][pos];
	if( pa.first == x && -1 < pa.second )
		return pa.second;

	int result = 0;

	int p = price[pos++];
	int s = x / p;

	if( price.size() == pos ) {

		if( s*p == x ) {
			result = 1;
			// cout << "(" << p << "*" << s << ")";
		}
		
		
	} else {

		for( int i = 0; i <= s; i++ ) {

			int t = i * p;
			result = solve(x-t, pos);
			if( result ) {
				// cout << "(" << p << "*" << i << ")";
				break;
			}
		}
	}

	pa.first = x;
	pa.second = result;
	return result;
}

int main(int argc, char* argv[])
{
	while(1) {

		int n; cin >> n;
		int x; cin >> x;

		if( n == 0 && x == 0)
			break;
	
		for( int i = 0; i < n; i++ ) {
			int p; cin >> p;
			price.push_back(p);
		}

		mk_primes(x);

		for( int i = 0; i < S; i++ ) {
			for( int j = 0; j < L; j++ ) {			
				memo[i][j] = make_pair(-1,-1);
			}
		}

		for( auto p : primes ) {
			if( solve(p, 0) ) {
				cout << p << endl;
				goto LAST;
			}
		}

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
bool FF[1000002];
int main(){

	for(int i=3;i<1000001;i+=2){FF[i]=true;
		for(int j=3;j*j<=i;j+=2)
			if(i%j==0){FF[i]=false;break;}
}
	FF[2]=true;
	int Q,M;
	while(1){
		cin>>Q>>M;if(Q==0&&M==0)break;

		int D[35]={};
		bool F[1000002];
		for(int i=0;i<Q;i++)
			cin>>D[i];
		int P=0;
		for(int i=0;i<=M;i++)
			F[i]=false;

		for(int i=0;i<Q;i++){
			for(int j=0;j<=M;j++)
			{
				
				if(j==D[i])F[j]=true;
				if(j-D[i]>0&&F[j-D[i]]==true)F[j]=true;
				if(F[j]==true&&FF[j]==true)P=j;
			}}
		if(P>0)cout<<P<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}

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

using namespace std;

bool is_prime[2000000];
bool is_able[2000000];

int main(){
	
	int N = 1000001;
	
	for(int i = 0; i < N; i++){
		is_prime[i] = true;
	}
	
	is_prime[0] = false;
	is_prime[1] = false;
	
	for(int i = 2; i < N; i++){
		if(is_prime[i]){
			for(int j = i * 2; j < N; j += i){
				is_prime[j] = false;
			}
		}
	}
	
	int n, x;
	
	while(true){
		
		cin >> n >> x;
		
		if(n == 0 && x == 0){
			break;
		}
		
		int v[200];
		
		for(int i = 0; i < n; i++){
			cin >> v[i];
		}
		
		for(int i = 0; i <= x; i++){
			is_able[i] = false;
		}
		
		is_able[0] = true;
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= x - v[i]; j++){
				if(is_able[j]){
					is_able[j + v[i]] = true;
				}
			}
		}
		
		int ans = 0;
		
		for(int i = x; i >= 0; i--){
			if(is_able[i] && is_prime[i]){
				ans = i;
				break;
			}
		}
		if(ans == 0){
			cout << "NA" << endl;
		}else{
			cout << ans << endl;
		}
		
	}
	
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
const int MAX_INT = 1000000;
bool er[1000001];
int n,x,ans;
int v[31];
int solve(int k,int m);
int memo[1000001];
int main(){
  memset(er,true,sizeof(er));
  for(int i=2;i<=sqrt(MAX_INT);i++){
    if(er[i]){
      for(int j=0;i*(j+2)<MAX_INT;j++){
	er[i*(j+2)]=false;
      }
    }
  }
  while(cin >> n >> x, n|x){
    if(!n && !x)break;
    memset(memo,-1,sizeof(memo));
    for(int i=0;i<n;i++){
      cin >> v[i];
    }
    
    ans = solve(0,0);
    if(!ans)cout << "NA\n";
    else cout << ans << endl;
  }
}
int solve(int k,int m){
  if(memo[m] != -1)return memo[m];
  if(m > x)return 0;
  else if(k == n){
    if(m == 0)return 0;
    if(er[m])return m;
    else return 0;
  }
  return memo[m] = max(solve(k,m+v[k]),solve(k+1,m));
}

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++){
			num[ food[i] ]=1;
		}
		for(int i=0;i<X+1;i++){
			if( num[i]!=0){
				for(int j=0;j<N;j++){
					if( i+food[j]>=num.size())break;
					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<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,n) for(int i=1;i<=n;i++)

int sosu[1111111];
int dp[1211111];
int main(){
	
	sosu[0]=1;
	sosu[1]=1;
	
	for(int i=2;i<1111111;i++){
		if(sosu[i]==1)continue;
		for(int j=i+i;j<1111111;j+=i){
			sosu[j]=1;
		}
	}
	
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		rep(i,1111111)dp[i]=0;
		dp[0]=1;
		
		int item[33];
		rep(i,n){
			cin>>item[i];
		}
		
		int ans=-1;
		rep(i,m+1){
			if(dp[i]==0)continue;
			if(sosu[i]==0)ans=i;
			rep(j,n){
				if(i+item[j]>m)continue;
				dp[i+item[j]]=1;
			}
		}
		if(ans==-1){
			puts("NA");
		}else{
			printf("%d\n",ans);
		}
	}
}