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>
#include<cstring>

using namespace std;

bool prime[1000001];
bool dp[1000001];
int menu[31];
void seive(int s){
	for(int i=0;i<=s;i++)prime[i]=true;
	prime[0]=prime[1]=false;
	for(int i=2;i<=s;i++){
		if(prime[2]==true){
			for(int j=i*2;j<=s;j+=i){
				prime[j]=false;
			}
		}
	}
}

int main(void){
	seive(1000000);
	int n,x;
	while(1){
		int max=0;
		memset(dp,false,sizeof(dp));
		scanf("%d%d",&n,&x);
		if(n==0 && x==0)break;
		for(int i=0;i<n;i++){
			scanf("%d",&menu[i]);
		}
		dp[0]=true;
		for(int i=0;i<n;i++){
			for(int j=menu[i];j<=x;j++){
				if(dp[j-menu[i]]==true)dp[j]=true;
			}
		}
		for(int i=0;i<=x;i++){
			if(dp[i]==true && prime[i]==true)max=i;
		}
		if(max>0)printf("%d\n",max);
		else printf("NA\n");
	}
    return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <stack>
#include <list>

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,b,n) for(int i=b;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

bool dp[1000001], sosu[1000001];
int n, x;
int v[30];

void sosuu() {
  sosu[0]=false;
  for(int i=2; i*i<=x; i++) {
    if (sosu[i]) {
      for (int j=2*i; j<=x; j+=i) {
        sosu[j] = false;
      }
    }
  }
}
  

int main() {
  while(cin >> n >> x, n) {
    rep(i, n)
      cin >> v[i];
    rep(i, x+1) {
      sosu[i] = true;
      dp[i] = false;
    }
    sosuu();
    rep(i, n) {
      dp[v[i]]=true;
      for(int j=v[i]; j<=x; j++)
        if(dp[j])
          dp[j+v[i]] = true;
    }
    while(x>0) {
      if(dp[x] && sosu[x])
        break;
      x--;
    }
    if(x==0)
      cout << "NA" << endl;
    else
      cout << x << endl;
  }

  return 0;
}

C++: from datetime import datetime

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

input = raw_input
range = xrange
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)
    
    for i in range(2, n):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i + i, n, i):
                table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)

    def get(i):
        return ((dp[i >> 5] >> (i & 31)) & 1)

    def set(i, v):
        dp[i >> 5] |= (v << (i & 31))

    def get_p(i):
        return dp[i >> 5]
    def set_p(i, v):
        dp[i >> 5] |= v
        
    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        
        for p in range(cur_p, price + 1, 32):
            i1 = (p - cur_p) >> 5
            i2 = p >> 5
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            
            rest = (v >> (32 - r)) & ((1 << r) - 1)
            
    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and get(i) == 1:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, table)

main()

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[30],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<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int n, x, ans;
int in[31];
bool dp[1000001];
vector<int> v;
void solve(int a, int sum){
	for (int i = a; i <= n; i++){
		if (sum + in[i] <= x){
			if (dp[sum + in[i]])
				continue;
			if (sum + in[i] % 2 && sum + in[i] % 3){
				dp[sum + in[i]] = 1;
			}
			solve(i, sum + in[i]);
		}
	}
}
int main(){
	while (cin >> n >> x&&n&&x){
		ans = 0;
		fill(dp, dp + 1000001, 0);
		for (int i = 1; i <= n; i++)
			cin >> in[i];
		solve(1, 0);
		for (int i = x; i > 0; i--){
			if (dp[i]){
				for (int j = 5; j <= x; j++){
					if (j == i)
						ans = j;
					if (i % j == 0)
						break;
				}
				if (ans)
					break;
			}
		}
		if (ans)
			cout << ans << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
#define KMAX 30
#define VMAX 1000000
int main( void )
{
	vector <bool> prime(VMAX+1, false);
	for ( int i = 3; i <= VMAX; i += 2 )
	{
		prime[i] = true;
	}
	prime[2] = true;
	for ( int i = 3; i * i <= VMAX; i += 2 )
	{
		if ( prime[i] )
		{
			for ( int j = i + i; j <= VMAX; j += i )
				prime[j] = false;
		}
	}

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

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

		vector < vector <bool> > T( KMAX, vector <bool>(VMAX, false) );

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

		for ( int i = 1; i < n; i++ )
		{
			for ( int j = 1; j < K[i]; j++ )
			{
				T[i][j] = T[i-1][j];
			}

			for ( int j = K[i]; j <= x; j++ )
			{
				T[i][j] = ( T[i-1][j] || T[i][j-K[i]] );
			}
		}

		int kotae = -1;
		for ( int i = x; i >= 2; i-- )
		{
			if ( prime[i] && T[n-1][i] )
			{
				kotae = i;
				break;
			}
		}

		if ( kotae == -1 )
			cout << "NA" << endl;
		else
			cout << kotae << endl;

	}

	return 0;
}