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 "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

bool isso(long long int a) {
	if (a == 1 || a == 0)return false;
	for (long long int i = 2; i*i <= a; ++i) {
		if ((a%i)) {
		}
		else {
			return false;
		}
	}
	return true;
}
int main() {
	while (1) {
		int N, X; cin >> N >> X;
		if (!N)break;
		vector<int>as;
		for (int i = 0; i < N; ++i) {
			int a; cin >> a;
			as.emplace_back(a);
		}
		vector<int>oks(2000000);
		oks[0] = true;
		for (int i = 0; i <= X; ++i) {
			if (oks[i]) {
				for (int j = 0; j < N; ++j) {
					oks[i + as[j]] = true;
				}
			}
		}
		int ans = -1;
		for (int i = X; i >= 2; --i) {
			if (oks[i] && isso(i)) {
				ans = i;
				break;
			}
		}
		if (ans == -1)cout << "NA" << endl;
		else cout << ans << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <list>
#include <map>
#include <cmath>

using namespace std;

vector<int> price;
list<int> primes;

const int M = 1000000;
const int L = 30;
const int D = 10;
const int S = M/D;
pair<int,int> memo[S][L];

void mk_primes(int x)
{
	for( int i = 3; i <= x; i+=2 ) {
		for( int j = 3; j <= sqrt(i); j++ ) {
			if( i % j == 0 ) {
				goto NEXT;
			}
		}
		primes.push_front(i);
	NEXT:;		
	}
}

int solve(int x, int pos)
{
	pair<int,int>& pa = memo[x%S][pos];
	if( pa.first == x && -1 < pa.second )
		return pa.second;

	int result = 0;

	int p = price[pos++];
	int s = x / p;

	if( price.size() == pos ) {

		if( s*p == x ) {
			result = 1;
			// cout << "(" << p << "*" << s << ")";
		}
		
		
	} else {

		for( int i = 0; i <= s; i++ ) {

			int t = i * p;
			result = solve(x-t, pos);
			if( result ) {
				// cout << "(" << p << "*" << i << ")";
				break;
			}
		}
	}

	pa.first = x;
	pa.second = result;
	return result;
}

int main(int argc, char* argv[])
{
	while(1) {

		int n; cin >> n;
		int x; cin >> x;

		if( n == 0 && x == 0)
			break;
	
		for( int i = 0; i < n; i++ ) {
			int p; cin >> p;
			price.push_back(p);
		}

		mk_primes(x);

		for( int i = 0; i < S; i++ ) {
			for( int j = 0; j < L; j++ ) {			
				memo[i][j] = make_pair(-1,-1);
			}
		}

		for( auto p : primes ) {
			if( solve(p, 0) ) {
				cout << p << endl;
				goto LAST;
			}
		}

		cout << "NA" << endl;

	LAST:;

		price.clear();

	}

    return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
#define MOD 1e9 + 7

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;

#define MAX 1000000

bool prime[1000000];
int N, X;
int price[30];
int dp[MAX + 1];

void PrimeJudge() {
	memset(prime, true, sizeof(prime));
	prime[0] = false;
	FOR(i, 1, sqrt(MAX)) {
		if(prime[i]) {
			for(int j = (i + 1); (i + 1) * j <= MAX; ++j) {
				prime[(i + 1) * j - 1] = false;
			}
		}
	}
	return;
}

int main() {
	PrimeJudge();
	while(scanf("%d %d", &N, &X), N || X) {
		memset(dp, 0, sizeof(dp));
		rep(i, N) scanf("%d", &price[i]);
		rep(i, N) FOR(j, price[i], X + 1) {
			dp[j] = max(dp[j], dp[j - price[i]] + price[i]);
		}
		bool flag = false;
		for(int i = X; i >= 0; --i) if(dp[i] - 1 >= 0) {
			if(prime[dp[i] - 1]) {
				printf("%d\n", dp[i]);
				flag = true;
				break;
			}
		}
		if(!flag) printf("NA\n");
	}
	return 0;
}

C++: #include<iostream>
#include<vector>

using namespace std;

int main()
{
	char pri[1000000];
	int i,j;
	
	for(i=0;i<1000000;i++)
	{
		pri[i]='1';
	}
	pri[0]=pri[1]='0';
	
	for(i=0;i<1000000;i++)
	{
		if(pri[i]=='1')
		{
			for(j=2;j*i<1000000;j++)
			{
				pri[i*j]='0';
			}
		}
	}
	
	int n,max,menu[100];
	vector<char> sum;
	
	
	for(;;)
	{
		cin >> n >> max ;
		if(n==0 && max==0)
			break;
		int ans=0;
		sum.clear();
		for(i=0;i<1000000;i++)
			sum.push_back(0);
		
		for(i=0;i<n;i++)
		{
			cin >> menu[i];
			sum[menu[i]]='1';
		}
		
		for(i=0;i<=max;i++)
		{
			if(sum[i]=='1')
			{
				if(pri[i]=='1')
					ans=i;
				for(j=0;j<n;j++)
				{
					if(i+menu[j]<=max)
						sum[i+menu[j]]='1';
				}
			}
		}
		if(ans==0)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define INF (1111111)
int N,X;
int r[31];
bool sosu[1000001];
bool dp[1000001];
int solve(){
  /*  if(sum>X) return 0; 
  if(dp[sum]!=-1) return dp[sum];
  int ret=0;
  for(int i=0;i<N;i++){
    ret=max(ret,solve(sum+r[i]));
  }
  if(!sosu[sum]){
    return dp[sum]=max(sum,ret);
  }else{
    return dp[sum]=ret;
    } */
  int res=0;
  for(int i=0;i<N;i++) dp[r[i]]=true;
  for(int i=1;i<=X;i++){
    if(!dp[i]) continue;
    if(!sosu[i]) res=i;
    for(int j=0;j<N;j++){
      dp[i+r[j]]=true;
    }
  }
  return res;
}

main(){
  sosu[0]=true;
  sosu[1]=true;
  for(int i=2;i<1000001;i++){
    if(!sosu[i])
      for(int j=i*2;j<1000001;j+=i){
	if(j>1000000) break;
	sosu[j]=true;
      }
  }
  while(1){
    scanf("%d %d",&N,&X);
    if(N==0 && X==0) break;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
      scanf("%d",&r[i]);
    }
    sort(r,r+N);
        int res = solve();
    if(res==0) puts("NA");
    else printf("%d\n",res);
  }
}

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

#define MONEY_MAX 1000010

using namespace std;


int main(void){
  bool* prime=(bool*)malloc(MONEY_MAX*sizeof(bool));

  for(int i=0;i<MONEY_MAX;i++){
    prime[i]=true;
  }

  prime[0]=false;
  prime[1]=false;
  for(int i=2;i<sqrt(MONEY_MAX)+10;i++){
    if(prime[i]==false){continue;}
    int k=2;
    while(k*i<MONEY_MAX){
      prime[k*i]=false;
      k++;
    }
  }

  int n,x;
  while(true){
    cin>>n>>x;
    if(n==0 and x==0){break;}
    int v[n];
    for(int i=0;i<n;i++){
      cin>>v[i];
    }
    bool* table[n];
    for(int i=0;i<n;i++){
      table[i]=(bool*)malloc(sizeof(bool)*(x+1));
      for(int j=0;j<=x;j++){
        table[i][j]=false;
      }
    }
    for(int j=0;j<=x;j++){
      table[0][j]=(j%v[0]==0);
    }
    for(int i=1;i<n;i++){
      for(int j=0;j<=x;j++){
        if(j-v[i]>=0){
          table[i][j]=table[i-1][j] or table[i-1][j-v[i]] or table[i][j-v[i]];
        }
        else{
          table[i][j]=table[i-1][j];
        }
      }
    }
    for(int s=x;s>=0;s--){
      if(prime[s] and table[n-1][s]){
        cout<<s<<endl;
        break;
      }
      if(s==0){
        cout<<"NA"<<endl;
      }
    }
    for(int i=0;i<n;i++){
      free(table[i]);
    }
  }

  return 0;
}