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 <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 = 10;
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[])
{
	mk_primes(M);
	
	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);
		}

		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( x < p )
				continue;
			
			if( solve(p, 0) ) {
				cout << p << endl;
				goto LAST;
			}
		}

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
bool e[1000001],dp[1001110];
int main(){
  e[0]=e[1]=1;
  for(int i=2;i<1000001;i++)
    for(int j=i*2;j<1000001;j+=i)
      e[j]=1;
  int n,m;
  while(cin>>n>>m,n){
    for(int i=0;i<m+110;i++)dp[i]=0;
    int a[n],c=1,p;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
      for(int j=1;j<=m;j++){
        if(dp[j]&&a[i]+j<=m)dp[a[i]+j]=1;
        if(a[i]*j<=m)dp[a[i]*j]=1;}
    for(p=m;p>=0;p--)if(dp[p]&&!e[p]){c=0;break;}
    if(c)cout<<"NA"<<endl;
  else cout<<p<<endl;
  }
}

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

int is[1000001];
bool isprime[1000001];

int main() {

    isprime[0] = isprime[1] = true;
    for(int i=4; i<=1000000; i+=2) isprime[i] = true;
    for(int i=3; i*i<=1000000; i+=2)
        for(int j=2; i*j<=1000000; ++j)
            isprime[i*j] = true;

    int n,x,s;
    while(cin>>n>>x, n|x) {
        memset(is, -1, sizeof(is));
        is[0] = 0;
        for(int i=1; i<=n; ++i) {
            cin>>s;
            for(int j=0; j<=x; ++j) {
                if(is[j] >= i) continue;
                if(is[j] >= 0) {
                    for(int k=1; j+s*k <= x; ++k)
                        is[j+s*k] = i;
                }
            }
        }

        for(int j=x; j>=0; --j) {
            if(is[j] && !isprime[j]) {
                cout<<j<<endl;
                goto NEXT;
            }
        }
        cout<<"NA"<<endl;
    NEXT:;
    }
}

C++: #include <iostream>
#define N 1000000 
using  namespace std;

int main(void){
	bool isprime[N+1];
	for(int i=0;i<=N;i++)
		isprime[i]=true;
	isprime[0]=isprime[1]=false;
	for(int i=2;i<=N;i++)
		if(isprime[i])
			for(int j=2*i;j<=N;j+=i)
				isprime[j]=false;
	bool budget[N+1];
	int n,m;
	while(cin >> n>>m,n|m){
		for(int i=0;i<=m;i++)
			budget[i]=false;
		int tmp;
		budget[0]=true;
		for(int i=0;i<n;i++){
			cin >> tmp;
			for(int j=0;j<=m;j++)
				if(budget[j]&&(j+tmp)<=m)
					budget[j+tmp]=true;
		}
		int MAX=0;
		for(int i=m;i>0;i--){
			if(budget[i]&isprime[i]){
				MAX=i;break;
			}
		}
		if(MAX)
			cout << MAX << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<cmath>
using namespace std;
#define KMAX 30
#define VMAX 1000000
int K[KMAX];
unsigned char T[KMAX][VMAX+1];
void eratos ( int n, bool prime[]){
 for ( int i = 0; i <= n; i++ ) prime[i] = false;
 for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
 prime[2] = true;
 int limit = (int)sqrt((double)n) + 1;
 for ( int i = 3; i <= limit; i += 2 ){
if ( !prime[i] ) continue;
for ( int j = i + i; j <= n; j += i ) prime[j] = false;
 }
}
main(){
 bool prime[VMAX + 1];
 eratos( VMAX, prime );
 int k, v;
 while( cin >> k >> v && !(k == 0 && v == 0) ){
for ( int i = 0; i < k; i++ ) cin >> K[i];
for ( int j = 0; j <= v; j++ ) T[0][j] = 0;
for ( int j = K[0]; j <= v; j += K[0] ) T[0][j] = 1;
for ( int i = 0; i < k; i++ ) T[i][0] = 1;
for ( int i = 1; i < k; i++ ){
 for ( int j = 1; j < K[i]; j++ ) T[i][j] = T[i-1][j];
 for ( int j = K[i]; j <= v; j++ ){
T[i][j] = (T[i-1][j] | T[i][j-K[i]]);
 }
}
int ans = -1;
for ( int i = v; i >= 2; i-- ){
 if ( prime[i] && T[k-1][i] ) { ans = i; break; }
}
if ( ans == -1 ) cout << "NA" << endl;
else cout << ans << endl;
 }
}

C++: #include <bits/stdc++.h>
using namespace std;
bool dp[1000001];
bool a[1000001];
int main() {
    long long n, x;
    fill(a, a + 1000001, true);
    a[0] = false;
    a[1] = false;
    for (int i = 0; i <= 1000000; i++) {
        if (a[i]) {
            int j = 2;
            while (i*j <= 1000000) {
                a[i*j] = false;
                j++;
            }
        }
    }
    while (cin >> n >> x&&n != 0 && x != 0) {
        fill(dp, dp + x + 1, false);
        int y;
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            cin >> y;
            for (int i = y; i <= x; i++) {
                if (dp[i - y]) {
                    dp[i] = true;
                }
            }
        }
        for (int i = x; i >= 2; i--) {
            if (a[i]&&dp[i]) {
                cout << i << endl;
                goto finish_v;
            }
        }
        cout << "NA" << endl;
    finish_v:;
    }
}

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

bool p[1000010];
bool ok[1000010];

void mkprime() {
	for(int i = 0; i < 1000010; i++) {
		p[i] = true;
	}
	p[0] = p[1] = false;
	for(int i = 0; i*i <= 1000010; i++) {
		if(p[i]) {
			for(int j = i*2; j < 1000010; j += i) {
				p[j] = false;
			}
		}
	}
}

int main() {
	int n, x;

	mkprime();
	while(cin >> n >> x, n || x) {
		vector<int> v;
		for(int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}
		for(int i = 0; i < 1000010; i++) {
			ok[i] = false;
		}
		ok[0] = true;
		for(int i = 0; i < v.size(); i++) {
			for(int j = 0; j < x + 10; j++) {
				if(j - v[i] >= 0 && ok[j - v[i]]) {
					ok[j] = true;
				}
			}
		}

		bool flg = true;
		for(int i = x; i >= 0; i--) {
			if(ok[i] && p[i]) {
				flg = false;
				cout << i << endl;
				break;
			}
		}
		if(flg) {
			cout << "NA" << endl;
		}
	}
}