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<vector>
#include<iostream>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()

const int N = 1000001;
const int M = 30;

bool table[M][N];
bool isprime[N];

void generate(){
  for(int i=0;i<N;i+=2)isprime[i]=false;
  for(int i=1;i<N;i+=2)isprime[i]=true;
  isprime[2]=true;
  for(int i=3;i*i <= N ;i+=2){
    if (isprime[i]){
      for(int j=2*i;j<N;j+=i)isprime[j]=false;
    }
  }
}

void solve(int n,int lim,vector<int> & price){
  rep(i,n)rep(j,lim+1)table[i][j]=false;
  
  for(int i=0;i<lim+1;i+=price[0]){
    table[0][i]=true;
  }

  REP(i,1,price.size()){
    rep(j,lim+1){
      table[i][j]=table[i-1][j];
      if (j-price[i] < 0)continue;
      table[i][j]|=(table[i][j-price[i]]);
    }
  }

  for(int i=lim;i>0;i--){
    if (isprime[i] && table[n-1][i]){
      cout << i << endl;
      return;
    }
  }
  cout << "NA" << endl;
}


main(){
  int n;
  int lim;
  generate();
  while(cin>>n>>lim && n){
    vector<int> a;
    int tmp;
    rep(i,n){
      cin>>tmp;
      a.push_back(tmp);
    }
    solve(n,lim,a);
  }
  return false;
}

C++: #include <iostream>
using namespace std;
bool dp[5000000];
int menu[30];
int main()
{
    while(1)
    {
        int n,x;
        cin>>n>>x;if(!n)return 0;
        for(int i=0;i<n;++i){
            cin>>menu[i];
        }
        fill(dp,dp+5000000,false);
        dp[0]=true;
        for(int i=0;i<=x;++i){
            if(dp[i]){
                for(int j=0;j<n;++j){
                    dp[i+menu[j]]=true;
                }
            }
        }
        int m=0;
        for(int i=x;i>=0;--i){
            bool flag=true;
            if(dp[i]){
                for(int j=2;j*j<=i;++j){
                    if(!(i%j)){
                        flag=false;
                    }
                }
                if(flag){
                    m=i;
                    break;
                }
            }
        }
        if(m)cout<<m<<endl;
        else cout<<"NA"<<endl;
    }
}

C++: #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

const int LIM=1000010;

bool sosu[LIM];
int ok[LIM];

int main() {
	int i,j;
	for(i=0;i<LIM;i++){
		sosu[i]=true;
	}
	sosu[0]=sosu[1]=false;
	for(i=0;i<LIM;i++){
		if(sosu[i]){
			for(j=i*2;j<LIM;j+=i){
				sosu[j]=false;
			}
		}
	}
	int n,x;
	while(n=in(),x=in()){
		int c;
		memset(ok,0,sizeof(ok));
		ok[0]=1;
		for(i=0;i<n;i++){
			cin>>c;
			for(j=c;j<LIM;j++){
				if(ok[j-c]){
					ok[j]=1;
				}
			}
		}
		for(;!sosu[x]||!ok[x];){
			x--;
			if(x==0)break;
		}
		if(x==0)cout<<"NA\n";
		else cout<<x<<endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std ;
void ans( int cnt ,int dp[] )
{
	int a = cnt ;
	LOOK :
	a-- ;
	while( dp[ a ] != 1 )
	{
		a-- ;
		if( a < 2 )
		{
			END :
			cout << "NA" << endl ;
			return ;
		}
	}
	if( a < 2 )
	{
		goto END ;
	}
	if( a % 2 == 0 )
	{
		goto LOOK ;
	}
	if( a == 2 )
	{
		cout << a << endl ;
		return ;
	}
	for( int i = 3 ; i * i <= a ; i += 2 )
	{
		if( a % i == 0 )
		{
			goto LOOK ;
		}
	}
	cout << a << endl ;
	return ;
}
int main()
{
	int n ,m ;
	int dmon[ 30 ] ;
	int j ;
	while( cin >> n >> m , n )
	{
		int cnt = m ;
		int dp[ 1000000 ] = { 0 } ;
		for( int i = 0 ; i < n ; i++ )
		{
			cin >> dmon[ i ] ;
		}
		for( int i = 0 ; i + dmon[ 0 ] <= m ; )
		{
			for( j = 0 ; j < n && i + dmon[ j ] <= m ; j++ )
			{
				dp[ i + dmon[ j ] ] = 1 ;
			}
			i++ ;
			while( dp[ i ] != 1 )
			{
				i++ ;
			}
		}
		ans( cnt ,dp ) ; 
	}
	return 0 ;
}

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

bool prime[10000001];
bool dp[30][10000001];
int menu[30];
int n,x;

void make_prime()
{
  memset(prime,true,sizeof(prime));
  prime[0]=prime[1]=false;
  for(int i=2;i<10000001;i++)
    {
      if(prime[i])
	{
	  for(int j=i+i;j<10000001;j+=i)
	    prime[j]=false;
	}
    }
}
void make_dp(int i,int sum)
{
  ///   cout<<sum<<endl;
  if(dp[i][sum]|| sum>x || i>=n)
    return;
  for(int x=i;x>=0;x--)
    dp[x][sum]=true;
  make_dp(i,sum+menu[i]);
  make_dp(i+1,sum);
}

int main()
{
  make_prime();
  for(;cin>>n>>x,n;)
    {
      memset(dp,false,sizeof(dp));
      for(int i=0;i<n;i++)
	  cin>>menu[i];
      make_dp(0,0);
      int ans=-1;
      for(int i=x;i>0;i--)
	if(prime[i]&&dp[0][i])
	  {
	    ans=i;
	    break;
	  }
      if(ans!=-1)
	cout<<ans<<endl;
      else
	cout<<"NA"<<endl;
    }
}

C++: #include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 30)
using namespace std;

const int kN = 1000005;

void primeNumber(bool prime[kN]){
    rep(i,kN) prime[i] = 1;
    prime[0] = prime[1] = 0;
    rep(i,kN){
        if(prime[i]){
            for(int j = i + i; j < kN; j+=i){
                prime[j] = 0;
            }
        }
    }
}

void primeOfCuisine(int n, int a[40], bool prime[kN]){
    prime[0] = 1;
    rep(i,n){
        rep(j,kN){
            if(prime[j] == 1){
                prime[j + a[i]] = 1;
            }
        }
    }
}

void outputAns(bool a[kN], bool b[kN], int x){
    for(int i = x; i >= 0; i--){
        if(a[i] == 1 && b[i] == 1){
            cout << i << endl;
            return;
        }
    }
    cout << "NA" << endl;
    return;
}

int main(){
    int n, x, a[40];
    while(cin >> n >> x, n||x){
        bool is_prime[kN] = {0};
        bool is_prime_of_cuisine[kN] = {0};
        rep(i,n) cin >> a[i];
        primeNumber(is_prime);
        primeOfCuisine(n, a, is_prime_of_cuisine);
        outputAns(is_prime, is_prime_of_cuisine, x);
    }
}