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] != -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>
#include <algorithm>
#include <cstring>

constexpr int MAX_N = 31, MAX_C = 1000001;
int n, max;
int cost[MAX_N];
bool dp[MAX_C];
bool prime_num[MAX_C];

int main() {
	while (1) {
		std::cin >> n >> max;
		if (n + max == 0)
			break;
		std::memset(prime_num, false, sizeof(prime_num));
		std::memset(dp, false, sizeof(dp));
		for (int i = 0; i < n; ++i)
			std::cin >> cost[i];
		for (int i = 2; i * i <= max; ++i) {
			if (!prime_num[i]) {
				for (int j = 2; i*j <= max; ++j)
					prime_num[i*j] = true;
			}
		}
		int ans = 0;
		for (int i = 0; i < n; ++i)
			dp[cost[i]] = true;

		for (int i = 1; i <= max; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i + cost[j] <= max&&dp[i])
					dp[i + cost[j]] = true;
			}
		}
		for (int i = max; i >= 0; --i) {
			if (dp[i] && !prime_num[i]) {
				ans = i; 
				break;
			}
		}
		if (!ans)
			std::cout << "NA" <<std::endl;
		else
			std::cout << ans << std::endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
int dp[1000001],flg[1000001];
int main(void)
{
	for(int i=2;i<=1000000;i++) flg[i]=1;
	for(int i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(int j=2;j*i<1000000;j++) flg[i*j]=0;
		}
	}
	int kin[31],n,x;
	while(1) {
		cin>>n>>x;
		if(n==0 && x==0) break;
		for(int i=0;i<n;i++) cin>>kin[i];
		for(int i=0;i<=x;i++) dp[i]=0;
		dp[0]=1;
		for(int i=0;i<n;i++) {
			for(int j=0;j<=x;j++) if(dp[j]==1) dp[j+kin[i]]=1;
		}
		;
		int data,no=0;
		for(int i=x;i>1;i--) {
			if(flg[i]==1 && dp[i]==1){data=i;no=1;break;}
		}
		if(no==0) cout<<"NA"<<endl;
		else cout<<data<<endl;
	}
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
bool FF[1000002];
int main(){

	for(int i=3;i<1000001;i+=2){FF[i]=true;
		for(int j=3;j*j<=i;j+=2)
			if(i%j==0){FF[i]=false;break;}
}
	FF[2]=true;
	int Q,M;
	while(1){
		cin>>Q>>M;if(Q==0&&M==0)break;

		int D[35]={};
		bool F[1000002];
		for(int i=0;i<Q;i++)
			cin>>D[i];
		int P=0;
		for(int i=0;i<=M;i++)
			F[i]=false;

		for(int i=0;i<Q;i++){
			for(int j=2;j<=M;j++)
			{
				
				if(j==D[i])F[j]=true;
				if(j-D[i]>0&&F[j-D[i]]==true)F[j]=true;
				if(F[j]==true&&FF[j]==true)P=j;
			}}
		if(P>0)cout<<P<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <limits>
#include <cstring>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

#define LIMIT 1000010
using namespace std;

bool isnotprime[LIMIT] = {0};
bool dp[40][LIMIT] = {0};
int n, x;
int dishes[100];

void erathos()
{
	CLR(isnotprime);
	
	FOR(i, 2, LIMIT)
	{
		if( !isnotprime[i] )
		{
			for(int j = 2; i*j < LIMIT; j++)
			{
				isnotprime[i*j] = true;
			}
		}
	}
	
	return;
}

int solve()
{
	int res = 0;
	
	CLR(dp);
	
	FOR(j, 0, n)
	{
		for(int i = dishes[j]; i <= x; i += dishes[j])
		{
			dp[j][i] = true;
		}
		
		if( j > 0 )
			for(int i = 1; i <= x; i++)
			{
				if(  ( dp[j-1][i] ) || ((i - dishes[j] > 0) && dp[j-1][i - dishes[j]]) )
				{
					dp[j][i] = true;
				}
			}
	}
	
	RFOR(i, 0, x+1)
	{
		if( !isnotprime[i] && dp[n-1][i] )
		{
			res = i;
			break;
		}
	}
	
	return res;
}

int main()
{
	erathos();
	
	while(cin >> n >> x, (n||x))
	{
		FOR(i, 0, n)
		{
			cin >> dishes[i];
		}
		
		int r = solve();
		
		if(r != 0)
			cout << r << endl;
		else
			cout << "NA" << endl;
	}
		
	return 0;
}

C++: // 2011/08/02 Tazoe

#include <iostream>
using namespace std;

void eratos(bool prm[], int n)
{
	if(n>=1)
		prm[0] = false;
	if(n>=2)
		prm[1] = false;

	for(int i=2; i<n; i++)
		prm[i] = true;

	for(int i=2; i<n; i++)
		if(prm[i])
			for(int j=i+i; j<n; j+=i)
				prm[j] = false;
}

int main()
{
	bool prm[1000001];
	eratos(prm, 1000001);

	while(true){
		int n, x;
		cin >> n >> x;
		if(n==0&&x==0)
			break;

		int K[30];
		for(int i=0; i<n; i++)
			cin >> K[i];

		bool DP[1000001];
		DP[0] = true;
		for(int i=1; i<=x; i++)
			DP[i] = false;

		for(int i=0; i<n; i++)
			for(int j=0; j<=x; j++)
				if(DP[j]&&j+K[i]<=x)
					DP[j+K[i]] = true;

		int ans = -1;
		for(int i=x; i>=0; i--)
			if(DP[i]&&prm[i]){
				ans = i;
				break;
			}

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

	return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

bool dp[1000000];

const int MAX_N = 1000000;

vector<int> prime;
bool is_prime[MAX_N+1];

// n以下の素数を生成する
void create_prime(int n){
	// 初期化
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<=n;i++){
		is_prime[i] = true;
	}
	
	for(int i=2;i<=n;i++){
		if(is_prime[i]){
			prime.push_back(i);
			for(int j=2*i;j<=n;j+=i){
				is_prime[j] = false;
			}
		}
	}
}

int main(){
	int n,x;
	create_prime(MAX_N);
	while(true){
		cin >> n >> x;
		if(n==0 && x==0) break;
		REP(i,x+1){
			dp[i] = false;
		}
		VI data;
		int buf;
		REP(i, n){
			cin >> buf;
			data.PB(buf);
		}

		dp[0] = true;
		REP(i,x){
			if(dp[i]){
				REP(j, n){
					if(i+data[j] < x) dp[i+data[j]] = true;
				}
			}
		}

		int ans = 0;
		REP(i, prime.size()){
			if(x <= prime[i]) break;
			if(dp[prime[i]]){
				ans = prime[i];
			}
		}

		if(ans != 0){
			cout << ans << endl;
		}else{
			cout << "NA" << endl;
		}
	}
}