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 <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, x, a[30]; bool dp[1000001], prime[1000001]; vector<int> p;
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;
	}
	p = {0};
	for(int i = 2; i <= 1000000; i++) {
		if(prime[i]) p.push_back(i);
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n);
		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 && i >= a[j]; j++) {
				if(dp[i - a[j]]) {
					dp[i] = true; break;
				}
			}
		}
		int pos = upper_bound(p.begin(), p.end(), x) - p.begin();
		for(int i = pos - 1; i >= 0; i--) {
			if(dp[p[i]]) {
				printf(i ? "%d\n" : "NA\n", p[i]); break;
			}
		}
	}
}

C++: #include<stdio.h>
int n,x;
int kin;
int i,j;
int dp[1000001];
int flg[1000001];
int main(void){
	for(i=1;i<=1000000;i++){
		flg[i]=1;
	}
	for(i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<=1000000;j++){
				flg[i*j]=0;
			}
		}
	}
	scanf("%d %d",&n,&x);
	while(n!=0 && x!=0){
		for(j=0;j<=x;j++){
			if(j>0){
				dp[j]=-1;
			}
			else if(j==0){
				dp[j]=0;
			}
		}
		for(i=0;i<n;i++){
			scanf("%d",&kin);
			for(j=0;j<=x;j++){
				if(dp[j]!=-1){
					dp[j+kin]=1;
				}
			}
		}
		int max=0;
		for(i=0;i<=x;i++){
			if(dp[i]==1 && flg[i]==1){
				max=i;
			}
		}
		if(max==0){
			printf("NA\n");
		}
		else {
			printf("%d\n",max);
		}
		scanf("%d %d",&n,&x);
	}
	return 0;
}

C++: #include <iostream>
#define MAX 1000001
#define INF 1<<27
using namespace std;
bool isPrime(int n){
  if(n == 0 || n == 1)return false;
  for(int i = 2 ; i*i <= n ; i++ ){
    if(n%i == 0)return false;
  }
  return true;
}

int main(){
  int n,yosan;
  int dp[MAX];
  while(cin >> n >> yosan,n){
    fill(dp,dp + MAX,0);
    dp[0] = 1;
    for(int i = 0 ; i < n ; i++ ){
      int a;
      cin >> a; 
      for(int j = a ; j <= yosan ; j++ ){
	if( dp[j - a] )dp[j] = 1;
      }
    }
    int res = -1;
    for(int i = yosan ; i >= 0 ; i-- ){
      if( isPrime(i) && dp[i] ){
	res = i;
	break;
      }
    }
    if(res == -1)cout << "NA" << endl;
    else cout << res << endl; 
  }
}

C++: //============================================================================
// Name        : DPpractice.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>
using namespace std;

int n, x;
int v[55] = {0};
bool dp[55][1000005];
int p[1000005] = {0};

int main() {
	while(true){
	for(int i = 2; i < 1000005; i++){
		if(p[i] == 0){
			int now = 2;
			while(now * i < 1000005){
				p[i * now] = 1;
				now++;
			}
		}
	}
	cin >> n >> x;
	if(n == 0 && x == 0) return 0;
	std:memset(dp, false, sizeof(dp));
	for(int i = 0; i < n; i++) cin >> v[i];
	dp[0][0] = true;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= x; j++){
			if(dp[i][j]){
				int now = 0;
				while(j + now * v[i] <= x){
					dp[i + 1][j + now * v[i]] = true;
					now++;
				}
			}
		}
	}
	int res = 0;
	for(int i = 2; i <= x; i++){
		if(dp[n][i]){
			if(p[i] == 0) res = i;
		}
	}
	if(res == 0){
		cout << "NA" << endl;
		continue;
	}
	cout << res << endl;
}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
	int n, x;

	vector< bool > p(1000001, true);
	p[1] = false;
	for(int i = 1; i * i <= 1000000; i++) {
		if(p[i] == true) {
			for(int j = 2; i * j <= 1000000; j++) {
				p[i * j] = false;
			}
		}
	}

	while( true ) {
		cin >> n >> x;

		if(n == 0 && x == 0) {
			break;
		}

		vector< int > num(n);

		for(int i = 0; i < n; i++) {
			cin >> num[i];
		}

		vector< vector< bool > > ans(n + 1, vector< bool >(x + 1, false));

		for(int i = 0; i < n - 1; i++) {
			for(int j = 0; j <= x; j++) {
				if(j < num[i]) {
					ans[i + 1][j] = ans[i][j];
				} else {
					ans[i + 1][j] = ans[i][j] | (ans[i + 1][j - num[i]] + num[i]);
				}
			}
		}

		int money = 0;
		for(int j = 0; j <= x; j++) {
			if(p[j]) {
				money = max(money, j);
			}
		}
		if(money != 0) {
			cout << money << endl;
		} else {
			cout << "NA" << endl;
		}
	}
}

C++: #include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

typedef long long int64;

int main()
{
	static bool noprime[1000001] = {false};
	
	noprime[0] = true;
	for(int i = 2; i * i <= 1000000; ++i) {
	
		if(!noprime[i]) {
		
			for(int j = i * 2; j <= 1000000; j += i)
				noprime[j] = true;
		}
	}

	while(true) {
	
		int n, x;
		int v[30];
		
		scanf("%d%d", &n, &x);
		if(n == 0 && x == 0)
			break;
		for(int i = 0; i < n; ++i)
			scanf("%d", v + i);
			
		static bool dp1[1000001], dp2[1000001];
		bool *prev = dp1;
		bool *next = dp2;
		
		fill(dp1, dp1 + (x + 1), 0);
		fill(dp2, dp2 + (x + 1), 0);
		
		for(int i = 0; i < n; ++i) {
			
			next[0] = prev[0] = true;
		
			for(int c = 1; c <= x; ++c)
				next[c] = prev[c];
			
			for(int c = v[i]; c <= x; ++c)
				next[c] = (next[c] || next[c - v[i]]);
				
			swap(next, prev);
		}
		
		int ans = -1;
		
		for(int i = x; i > 0; --i) {
		
			if(!noprime[i] && prev[i]) {
				ans = i;
				break;
			}
		}
		
		if(ans < 0)
			printf("NA\n");
		else
			printf("%d\n", ans);
	}
	
	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
bool dp[1000001]={true},prime[1000001]={true,true};
int solve(int &i){
  while(i--) if(dp[i] && !prime[i]) return i;
}
int main(){
  int n,x,data[30],ans;
  for(int i = 2 ; i * i < 1000001 ; i++ ){
    if(!prime[i]) for(int j = 2 ; i * j <= 1000001 ; j++ ) prime[i*j] = true;
  }
  while(cin >> n >> x , n){
    for(int i = 1 ; i <= x ; i++ ) dp[i] = false;
    for(int i = 0 ; i < n ; i++ ) cin >> data[i];
    for(int i = 0 ; i <= x ; i++ ){
      if(dp[i]) for(int j = 0 ; j < n ; j++ ) dp[i+data[j]] = true;
    }
    if(ans = solve(x)) cout << ans << endl;
    else cout << "NA" << endl;
  }
}