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<iostream>
#include<algorithm>
#include<cstring>
#define M 1111111
using namespace std;

int n, x;
int data[33];
int prim[M];
int flg[M];
int p;

void solve(int i){

  if(i == n || p > x) return;
  if(flg[p]) return;
  
  solve(i+1);

  p += data[i];
  solve(i);
  p -= data[i];

  p += data[i];
  solve(i+1);
  p -= data[i];

  flg[p] = 1;
}


  
int main(){

  prim[0] = prim[1] = 1;
  for(int i=2;i*i<M;i++)
    if(!prim[i]) for(int j=i+i;j<M;j+=i) prim[j] = 1;

  for( ; ; ){
    cin >> n >> x;

    if(!n && !x) break;
    
    for(int i=0;i<n;i++) cin >> data[i];

    memset(flg, 0, sizeof(flg));
    p = 0;
    
    solve(0);
  
    int ans = -1;
    for(int i=0;i<=x;i++)
      if(!prim[i] && flg[i]) ans = i;

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

  
}

C++: // 2011/01/14 Tazoe

#include <iostream>
using namespace std;

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

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

	for(int i=2; i<n; i++){
		if(!prime[i])
			continue;
		for(int j=i+i; j<n; j+=i)
			prime[j] = false;
		if(n<i*i)
			return;
	}
}

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 T[1000001];
		T[0] = true;
		for(int i=1; i<=x; i++)
			T[i] = false;

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

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

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

	return 0;
}

C++: #include<stdio.h>
int hideo[1000001] = { 0 };
int main(void)
{
	int  n, x, temp = 1,noyori=0,debu=0 , ruio[31] = { 0 };
	while (scanf("%d %d", &n, &x)) {
		if (n == 0 && x == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ruio[i]);
			hideo[ruio[i]] = 1;
		}
		while (temp != x) {
			if (hideo[temp] == 1) {
				for (int j = 1; j <= n; j++) {
					if (hideo[temp + ruio[j]] == 0) {
						hideo[temp + ruio[j]] = 1;
					}
				}
			}
			temp++;
		}
		for (int i = x; i >= 1; i--) {
			if (hideo[i] == 1) {
				for (int j = 2; j < i - 1; j++) {
					if (i%j == 0) {
						debu=1;
					}
				}
				if (debu == 0) {
					noyori = i;
					break;
				}
			}
			debu = 0;
		}
		if (noyori > 1 ) {
			printf("%d\n", noyori);
		}
		else {
			printf("NA\n");
		}
		temp = 1;
		noyori = 0;
		debu = 0;
		for (int i = 1; i <= n; i++) {
			ruio[i] = 0;
		}
		for (int i = 1; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

C++: #include<iostream>

bool prime[1000001], dp[1000001];

int main(){
	for(int i=0;i<=1000000;i++){
		prime[i] = true;
	}
	prime[0] = prime[1] = 0;
	for(int i=2;i*i<=1000000;i++){
		if(prime[i]){
			for(int j=i*2;j<=1000000;j+=i)prime[j] = false;
		}
	}

	int n, x, a[30];
	while(std::cin >> n >> x, n){
		for(int i=0;i<=x;i++){
			dp[i] = false;
		}

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

		int res = 0;

		dp[0] = true;
		for(int i=1;i<=x;i++){
			for(int j=0;j<n;j++){
				if(i-a[j] >= 0 && dp[i-a[j]]){
					dp[i] = true;
					break;
				}
			}
			if(dp[i] && prime[i]){
				res = i;
			}
		}

		if(res != 0){
			std::cout << res << std::endl;
		}else{
			std::cout << "NA" << std::endl;
		}
	}
}

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

int p[1000001];
int dp[1000001];
int main(){
	int n,x;
	while(cin >> n >> x && n){
		for(int i = 0 ; i < 1000001 ; i++) p[i] = 1 , dp[i] = 0;
		p[0] = p[1] = 0;
		for(int i = 1 ; i*i <= 1000000 ; i++){
			if( p[i] ){
				for(int j = i * i ; j <= 1000000 ; j+=i){
					p[j] = 0;
				}
			}
		}
		dp[0] = 1;
		for(int i = 0 ; i < n ; i++){
			int t;
			cin >> t;
			for(int j = t ; j < 1000001 ; j++){
				dp[j] |= dp[j-t];
			}
		}
		while(x>0 && (p[x] == 0 || dp[x] == 0) ){
			x--;
		}
		if( x == 0 ){
			cout << "NA" << endl;
		}else{
			cout << x << endl;
		}
	}
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int XMAX = 1000000;
constexpr int SQRTXMAX = (int)sqrt(XMAX);

bool is_prime[XMAX + 1];
bool dp[XMAX + 1];
int cost[30];

int main() {
  // prime
  memset(is_prime, true, sizeof(is_prime));
  is_prime[0] = is_prime[1] = false
  for (int i = 2; i <= SQRTXMAX) {
    if (is_prime[i]) {
      int current = i * i;
      for (int j = i * i; j <= XMAX; j += i) {
        is_prime[j] = false;
      }
    }
  }

  int n, x;
  while (cin >> n >> x, n) {
    for (int i = 0; i < n; i++) cin >> cost[i];

    // dp
    r = 0;
    dp[0] = true;
    for (int i = 1; i <= x; i++) {
      for (int j = 0; j < n; j++) {
        int k = i - cost[j];
        if (k >= 0 && dp[k]) {
          dp[i] = true;
          if (is_prime[i]) r = i;
          break;
        }
      }
    }

    if (r == 0) {
      cout << "NA" << endl;
    } else {
      cout << r << endl;
    }
  }
  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++ )
        if(i+data[j] <= x) dp[i+data[j]] = true;
    }
    if(ans = solve(x)) cout << ans << endl;
    else cout << "NA" << endl;
  }
}

C++: #include <iostream>
#include <string.h>
#include <set>
using namespace std;

const int LIMIT = 1000000;

int main()
{
	bool prime[ LIMIT + 1 ];
	memset( prime, false, sizeof(prime) );
	prime[ 0 ] = prime[ 1 ] = true;
	for( int i = 2; i < LIMIT + 1; ++i ){
		if( prime[ i ] ) continue;
		for( int j = i + i; j < LIMIT + 1; j += i ){
			prime[ j ] = true;
		}
	}

	int n, x;
	while( cin >> n >> x && ( n || x ) ){
		bool* price = new bool[ x + 1 ]();
		set< int > menu;
		for( int i = 0; i < n; ++i ){
			int p;
			cin >> p;
			if( p <= LIMIT ){
				menu.insert( p );
				price[ p ] = true;
			}
		}
		int ans = 0;
		for( int i = 0; i <= x; ++i ){
			if( !price[ i ] ) continue;
			if( !prime[ i ] ){
				ans = i;
			}
			set< int >::iterator itr = menu.begin();
			while( itr != menu.end() ){
				int a = i + *itr;
				if( a <= x ){
					price[ a ] = true;
				}
				++itr;
			}
		}

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

		delete [] price;
	}
	return 0;
}