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 <string.h>
#include <set>
using namespace std;

int main()
{
	bool prime[ 1000000 ];
	memset( prime, false, sizeof(prime) );
	prime[ 0 ] = prime[ 1 ] = true;
	for( int i = 2; i < 1000000; ++i ){
		if( prime[ i ] ) continue;
		for( int j = i + i; j < 1000000; 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;
			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;
}

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

int main(){
    bool nonprime[1000001] = {};
    nonprime[0] = nonprime[1] = true;
    for(int i = 2; i <= 1000000; i++){
        if(!nonprime[i]){
            for(int j = i+i; j <= 1000000; j += i){
                nonprime[j] = true;
            }
        }
    }
    
    while(1){
        int n, x;
        cin >> n >> x;
        
        if(n + x == 0)  break;
    
        bool valid[x+1] = {};
        valid[0] = true;
        
        int v;
        for(int i = 0; i < n; i++){
            cin >> v;
            for(int j = 0; j <= x-v; j++){
                if(valid[j])    valid[j+v] = true;
            }
        }
        
        int ans = -1;
        for(int i = x; i >= 1; i--){
            if(!nonprime[i]){
                ans = i;
                break;
            }
        }
        
        if(ans == -1)   cout << "NA" << endl;
        else            cout << ans << endl;
    }
    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<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;
    }
}