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 <algorithm>
#include <map>
#include <string>

using namespace std;

int dp[1000001];
int kind[31];


const int MAX_SIZE = 10000;
const int MAX_PRIME = 1000000;


int prime[MAX_PRIME+1];
bool isPrime[MAX_PRIME+1];
int p;

void erats(){
	// primeXgðú»
	fill(isPrime,isPrime+MAX_PRIME,true);
	p = 0;
	isPrime[0] = isPrime[1] = false;

	for(int i = 2; i <= MAX_PRIME; i++){
		if(isPrime[i]){
			prime[p++] = i;
		}
		else
			continue;

		// Óé¢É©¯é
		for(int j = 2*i; j <= MAX_PRIME; j+=i){
			isPrime[j] = false;
		}
	}
}


int main(){

	int n;
	int x;
	erats();
	while(cin>>n>>x&&!(n==0&&x==0)){
		for(int i = 0; i < n; i++){
			cin>>kind[i];
		}
		// eàzÌ¥¢ûª½íÞ é©ðßé
		fill(dp,dp+1000001,0);
		dp[0]=1;
		int maxCost=-1;

		//for(int j = 0; j < n; j++){
		//	for(int i = kind[j]; i <= x; i++){
		//		dp[i]+=dp[i-kind[j]];
		//	}
		//}

		for(int i = 1; i <= x; i++){
			dp[i]=0;
			for(int j = 0; j < n; j++){
				if(i-kind[j]>=0){
					dp[i]+=dp[i-kind[j]];
				}
			}
			//if(dp[i]>=1&&(isPrime[i])){
			//	maxCost=max(i,maxCost);
			//}
		}
		for(int i = 0; i <= x; i++){
			if(dp[i]&&isPrime[i])
				maxCost=i;
		}


		if(maxCost==-1)
			cout<<"NA"<<endl;
		else
			cout<<maxCost<<endl;
	}

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX = 1000000;
bool prime[1000001];
bool dp[31][1000001];

void Init(){
	for(int i = 0; i <= 30; i++){
		memset(dp[i], false, sizeof(dp[i]));
		dp[i][0] = true;
	}
}

void era(){
	prime[0] = prime[1] = false;
	for(int i = 2; i <= MAX; i++){
		if(prime[i]){
			for(int j = i*2; j <= MAX; j+=i) prime[j] = false;
		}
	}
}

int main(){
	int n, limit;
	memset(prime, true, sizeof(prime));
	era();
	while(cin >> n >> limit && ((n!=0)||(limit!=0))){
		Init();
		for(int i = 1; i <= n; i++){
			int tmp;
			cin >> tmp;
			int money = tmp;
			while(money <= limit){
				dp[i][money] = true;
				for(int j = 0; j <= limit; j++){
					if(money>j) dp[i][j] = dp[i-1][j]|dp[i][j];
					else dp[i][j] = dp[i][money]&dp[i-1][j-money]?true:dp[i][j]?true:false;
				}
				money += tmp;
			}
		}

		int maxc = 0;
		for(int i = 1; i <= n; i++){
			for(int j = limit; j >= 2; j--){
				if(dp[i][j]&&prime[j]&&maxc<j){
					maxc = j;
					break;
				}
			}
		}
		if(maxc == 0) cout << "NA" << endl;
		else cout << maxc << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <cstring>

using namespace std;

#define MAX_X 1000001
#define MAX_N 30

bool is_prime[MAX_X];

void init() {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAX_X; i++) 
        if (is_prime[i]) 
            for (int j = i+i; j < MAX_X; j+=i) 
                is_prime[j] = false;
}

bool can_make[MAX_X];

int n, x;
int dish[MAX_N];
bool input() {
    cin >> n >> x;
    if (n == 0 && x == 0) return false;
    for (int i = 0; i < n; i++) 
        cin >> dish[i];

    memset(can_make, 0, sizeof(can_make));
    can_make[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= x; j++) {
            if (j >= dish[i] && can_make[j-dish[i]])
                can_make[j] = true;
        }
    }
    return true;
}

int main() {
    init();
    while (input()) {
        bool found = false;
        while (x--) {
            if (is_prime[x] && can_make[x]) {
                cout << x << endl;
                found = true;
                break;
            }
        }
        if (!found) cout << "NA" << endl;
    }
    return 0;
}

C++: #include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n,x;
  while(cin>>n>>x,n+x){
    int ans=-1;
    bool dp[x+1000]={};
    vector<int>v(n);
    for(int i=0;i<n;i++){
      cin>>v[i];
      dp[v[i]]=true;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<x;i++){
      for(int j=0;j<v.size();j++){
	if(dp[i])
	if(i+v[j]>x){
	  v.pop_back();
	  j--;
	}else{
	  dp[i+v[j]]=true;
	}
      }
    }
    int num=x;
    if(num%2==0)num--;
    for(int i=num;i>1;i-=2){
      bool flag=true;
      if(dp[i]==true){
	for(int j=2;j<=sqrt(i);j++){
	  if(i%j==0){
	    flag=false;
	    break;
	  }
	}
	if(flag){
	  ans=i;break;
	}
      }
    }
    if(ans==-1&&dp[2]==false)
      cout<<"NA"<<endl;
    else if(ans!=-1)
      cout<<ans<<endl;
    else
      cout<<2<<endl;
  }
  return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

bool isPrime[1000001];
bool dp[1000001];
int main()
{
	fill(isPrime, isPrime+1000001, true);
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i < 1000001; ++i)
	{
		if (isPrime[i])
		{
			for (int j = 2*i; j < 1000001; j += i)
				isPrime[j] = false;
		}
	}

	int n, x;
	while (scanf("%d %d", &n, &x), n | x)
	{
		int v[30];
		for (int i = 0; i < n; ++i)
		{
			int t;
			scanf("%d", &t);
			v[i] = t;
		}

		fill(dp, dp+x+1, false);
		dp[0] = true;
		for (int i = 0; i <= x; ++i)
			if (dp[i])
				for (int j = 0; j < n; ++j)
					if (i + v[j] <= x)
						dp[i + v[j]] = true;

		int ans;
		for (ans = x; ans > 0; --ans)
			if (dp[ans] && isPrime[ans])
				break;
		if (ans)
			printf("%d\n", ans);
		else
			puts("NA");
	}

	return 0;
}

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] >= 0 && !isprime[j]) {
                cout<<j<<endl;
                goto NEXT;
            }
        }
        cout<<"NA"<<endl;
    NEXT:;
    }
}