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 <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;
const int MAX = 1000000;

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

	int n;
	while(scanf("%d", &n), n){
		int x;
		scanf("%d", &x);

		int p[30];
		rep(i, n)
			scanf("%d", &p[i]);

		int ans = -1;
		bool dp[1000001];
		dp[0] = true;
		reps(i, 1, x+1){
			dp[i] = false;
			rep(j, n){
				dp[i] |= i>=p[j] && dp[i-p[j]];
				if(dp[i]){
					if(isprime[i])
						ans = i;
					break;
				}
			}
		}

		if(ans == -1)
			puts("NA");
		else
			printf("%d\n", ans);
	}

	return 0;
}

C++: /*
 * src.cpp
 *
 *  Created on: 2016/07/29
 *      Author: joi
 */

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

const int MAX_N=30,MAX_X=1e6;

int n,x;
int l[MAX_N];

bool prime[MAX_X+1];

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

bool dp[MAX_X+1];

int main(){
	sieve();
	do{
		cin>>n>>x;
		if (n || x){
			REP(i,n){
				cin>>l[i];
			}
			memset(dp,0,sizeof(dp));
			dp[0]=true;
			REP(i,n){
				FOR(j,l[i],x+1){
					dp[j]|=dp[j-l[i]];
				}
			}
			int res=-1;
			for(int i=x;i>=1;i--){
				if (dp[i] && prime[i]){
					res=i;
					break;
				}
			}
			if (res==-1){
				cout<<"NA"<<endl;
			}else{
				cout<<res<<endl;
			}
		}
	}while (n || x);
	return 0;
}

C++: #include <iostream>
#include <cstdio>
using namespace std;
#define sosu 1000000
bool so[2000001];
int n,x,c[31];
bool his[2000001];
int ans;

void hantei() {
  so[0] = so[1] = 1;
  for(int i=2;i*i<=1000001;i++) 
    if(so[i] == 0) 
      for(int j=2;j<=1000001/i;j++)so[i*j] = 1;
}


void saiki(int sum) {
  his[sum] = 1;
  if(so[sum] == 0 && ans < sum) ans = sum;
  
  for(int i=0;i<n;i++) 
    if(c[i]+sum <= x && his[c[i]+sum] == 0) 
      saiki(c[i]+sum);
}


int main() {
  hantei();

  while(1){
    cin >> n >> x;
    if(n == 0 || x == 0) break;

    
    for(int i=0;i<n;i++) cin >> c[i];
    for(int i=0;i<=x+1;i++) his[i] = 0;
    
    ans = 1;
    saiki(0);
    
    if(ans == 1) cout <<"NA"<<endl;
    else cout << ans << endl;
    
  }
  
  return 0;
}

C++: #include <iostream>

using namespace std;

bool flag[1000001];
int n, x, m, price[30];

bool sosuu(int k) {
	if (k == 2) return true;
	else if (k < 2) return false;
	else if (k % 2 == 0) return false;
	for (int i = 3; i*i<=k; i += 2)
		if (k % i == 0) return false;
	return true;
}
void next(int p, int k) {
	if (flag[k]) return;
	flag[k] = true;
	if (k > x) return;
	if (k > m) if (sosuu(k)) m = k;
	if (p == n) return;
	for (int i = 0; k + price[p] * i <= x; ++i)
		next(p + 1, k + price[p] * i);
}

int main() {
	while (cin >> n >> x, n || x) {
		for (int i = 0; i < n; ++i)
			cin >> price[i];
		for (int i = 0; i < 1000001; ++i) flag[i] = false;
		m = 0;
		next(0, 0);
		if (m) cout << m << endl;
		else cout << "NA" << endl;
	}
	return 0;
}

C++: #include<iostream>
#include <cstdio>
#include<string>
#include<math.h>
using namespace std;
//int ha(string);
//int saga(int);
int q,m,n=1000000,List[1000];
bool  slist[1000001];
bool  klist[1000001];

int main()
{	
	int i,j,k,b=0,s,a=2,f=0,c=0;
	for( i = 0; i <n;i++ ){
		slist[i]=true;
		klist[i]=false;
	}

	i=0;
	while(i<sqrt((double)n)){
		for(i=a+a;i<n;i=i+a){
			slist[i]=false;
		}
		for(i=a+1;i<sqrt((double)n);i++){
			if(slist[i]==true){
				a=i;
				break;
			}
		}
	}
	cin>>m>>n;
	while(m!=0||n!=0){
	for( i = 0; i <n;i++ ){
		klist[i]=false;
	}
	for(i=0;i<m;i++){
		cin>>List[i];
		klist[List[i]]=true;
	}
		for(i=0;i<n;i++){
			if(klist[i]){
			for(j=0;j<m;j++){				
				klist[i+List[j]]=true;
			}
		}
	}
		for(i=n;i>0;i--){
			if(klist[i]&&slist[i]){
			break;
		}
	}
		if(i==0){
			printf("NA\n");
		}
		else{
		printf("%d\n",i);
		}
		cin>>m>>n;
	}
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i ++)
#define COUNT(i, n) for(int i = 1; i <= n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
 
using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;
const int N = 1000001;

int main(void){
    vector<bool> isP(N);
    fill(ALL(isP), true);
    rep(i, 2) isP[i] = false;
    for(int i = 2; i * i < N; i ++) if(isP[i]) for(int j = i * i; j < N; j += i) isP[j] = false;

    for(int n, x; cin >> n >> x, n;){
        vector<bool> dp(x + 1);
        fill(ALL(dp), false);
        dp[0] = true;
        while(n --){
            int m; cin >> m;

            rep(i, x - m + 1) if(dp[i]) dp[i + m] = true;
        }
        while(~x && !(dp[x] && isP[x])) x --;
     
        if(~x) cout << x << endl;
        else cout << "NA" << endl;
    }
 
    return 0;
}

C++: #include <stdio.h>
int n, x, a[30]; bool dp[1000001], prime[1000001];
int main() {
	for(int i = 2; i <= 1000000; i++) prime[i] = true;
	for(int i = 2; i <= 1000; i++) {
		if(!prime[i]) continue;
		for(int j = i * i; j <= 1000000; j += i) prime[j] = false;
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		for(int i = 0; i < x; i++) dp[i + 1] = false; dp[0] = true;
		for(int i = 1; i <= x; i++) {
			for(int j = 0; j < n; j++) {
				if(i - a[j] >= 0) dp[i] = dp[i] || dp[i - a[j]];
			}
		}
		bool flag = false;
		for(int i = x; i >= 1; i--) {
			if(dp[i]) {
				printf("%d\n", i); flag = true; break;
			}
		}
		if(!flag) printf("NA\n");
	}
}