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>

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<algorithm>
using namespace std;
int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    int menu[n];
    for(int i=0;i<n;i++){
      cin>>menu[i];
    }
    sort(menu,menu+n);
    reverse(menu,menu+n);
    int p = -1;
    bool money[x+1];
    money[0] = true;
    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]]){
	  money[i] = true;
	  break;
	}
      }
      if(money[i]&&prime[i])p=i;
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <vector>
#include <cmath>

using namespace std;

vector<int> primes;

void make_primes( int lim ) {
  vector<bool> vs( lim + 1 );
  fill( vs.begin(), vs.end(), true );
  vs[ 0 ] = vs[ 1 ] = false;
  const int l = (int)sqrt( lim );
  for ( int i = 2; i <= l; i++ ){
	if ( vs[ i ] ) {
	  for ( int j = i * i; j <= lim; j += i ) {
		vs[ j ] = false;
	  }
	}
  }
  for ( int i = 2; i <= lim; i++ ) {
	if ( vs[ i ] ) {
	  priems.push_back( i );
	}
  }
}

bool isPrime( int n ) {
  return binary_search( primes.begin(), primes.end(), n );
}

int main() {
  make_primes( 1000000 );
  while( true ) {
	int n, x;
	cin >> n >> x;
	if ( n == 0 and x == 0 ) break;
	vector<int> vs( n );
	for ( int i = 0; i < n; i++ ) {
	  cin >> vs[ i ];
	}
	sort( vs.begin(), vs.end() );
	vector<int> cs;
	cs.push_back( 0 );
	vector<int> indices( n );
	fill( indices.begin(), indices.end(), 0 );
	while( cs.back() <= x ) {
	  int mv = 100000000;
	  int mi = -1;
	  for ( int i = 0; i < n; i++ ) {
		if ( mv > cs[ indices[ i ] ] + vs[ i ] ) {
		  mi = i;
		  mv = cs[ indices[ i ] ] + vs[ i ];
		}
	  }
	  if ( cs.back() < mv ) {
		cs.push_back( mv );
	  } 
	  indices[ mi ]++;
	}
	reverse( cs.begin(), cs.end() );
	bool s = false;
	for ( int v : cs ) {
	  if ( isPrime( v ) ) {
		s = true;
		cout << v << endl;
		break;
	  }
	}
	if ( not s ) {
	  cout << "NA" << endl;
	}
  }
}

C++: require 'Prime'

loop do
  n, x = gets.split.map(&:to_i)
  break if n.zero? && x.zero?
  pb = [true]
  n.times.map{ gets.to_i }.each do |p|
    (0..x-p).each do |i|
      pb[i+p] = true if pb[i]
    end
  end

  na = true
  x.step(2, -1) do |i|
    if pb[i] && i.prime?
      puts i
      na = false
      break
    end
  end

  puts "NA" if na
end

C++: #include <iostream>
#include <vector>
using namespace std;
 
#define MAX_P 1000000
 
int main(){
    bool prime[MAX_P];
    prime[0] = false;
    prime[1] = false;
    for( int i = 2; i < MAX_P; i++ ) prime[i] = true;
    for( int i = 2; i < MAX_P; i++ ){
        if( prime[i] ){
            for( int j = 2*i; j < MAX_P; j += i ){
                prime[j] = false;
            }
        }
    }
    int n, x;
    while( cin >> n >> x, n || x ){
        vector<bool> dp(x+1);
        for( int i = 0; i <= x; i++ ) dp[i] = false;
        vector<int> p(n);
        for( int i = 0; i < n; i++ ){
            cin >> p[i];
        }
        dp[0] = true;
        int max = 0;
        for( int i = 0; i <= x; i++ ){
            if( dp[i] ){
                if( prime[i] && max < i ) max = i;
                for( int j = 0; j < n; j++ ){
                    if( i+p[j] <= x ) dp[i+p[j]] = true;
                }
            }
        }
        if( max > 0 ) cout << max << endl;
        else cout << "NA" << endl;
    }
}

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;
}