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])
		if n == 0 && x == 0 {
			break
		}
		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>
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);
    }
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000001
using namespace std;
int n, x;
int isprime[MAX];
int w[30];
int dp[MAX];
int main() {
    memset(isprime, 1, sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for (int i=2; i<MAX; i++) {
        if (isprime[i]) {
            for (int j=i*2; j<MAX; j+=i) isprime[j]=0;
        }
    }
    while (scanf("%d%d",&n,&x)) {
        if (n==0&&x==0) break;
        memset(dp, 0, sizeof(dp));
        for (int i=0; i<n; i++) scanf("%d",&w[i]);
        dp[0]=1;
        for (int i=0; i<=x; i++) {
            if (dp[i]) {
                for (int j=0; j<n; j++) {
                    if (i+w[j]<=x) dp[i+w[j]]=1;
                }
            }
        }
        int res=-1;
        for (int i=x; i>0; i--) {
            if (dp[i]&&isprime[i]) {
                res=i;
                break;
            }
        }
        if (res==-1) puts("NA");
        else printf("%d\n",res);
    }
}

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

bool prime[1000001];
void is_prime(int n){
	for(int i = 0; i <= n; ++i)
		prime[i] = true;
	prime[0] = prime[1] = false;
	
	for(int i = 2; i <= n; ++i){
		if(prime[i]){
			for(int j = i * 2; j <= n; j += i)
				prime[j] = false;
		}
	}
}

int memo[1000001];
int N, X, cook[50], ans;

int rec(int w){
	if(memo[w] != -1)
		return memo[w];
	if(prime[X - w])
		ans = max(ans, X - w);
	int res = 0;
	for(int i = 0; i < N; ++i){
		if(w - cook[i] >= 0)
			res = max(res, rec(w - cook[i]));
	}
	return memo[w] = res;
}

int main() {
	is_prime(1000000);
	while(cin >> N >> X && (N || X)){
		ans = 0;
		memset(memo, -1, sizeof(memo));
		
		for(int i = 0; i < N; ++i)
			cin >> cook[i];
			
		rec(X);
		if(ans == 0)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
	
	
	return 0;
}