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] != -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>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> PI;
#define MAX 1000009
ll m=0; int n=0; int ans=0;
bool flag;
/*void dfs(int num){
    if(flag) return;
    if(ans==num){flag=true;return;}
    if(num>ans){memo[num]=false;return;}
    else rep(i,n){
        cout<<num<<endl;
      if(num+v[i]<=ans&&memo[num+v[i]])dfs(num+v[i]);
    }
    memo[num]=false;
    return;
}*/
int main(){
    vector<bool>check(MAX+1);  //index number will be checked
    rep(i, MAX+1)check[i] = true;
    vector<int>Primenumber(MAX+1,0); //Primearray
    int counter =0;                  //Primearray counter;
    for(int i = 2; i<MAX+1;i++){
        if(check[i]){
            for(int j = 2;i*j<MAX;j++)
                check[i*j] = false;//?´???°??????Primearray???????´??????????????????°?????¨???false???
            Primenumber[counter] = i;
            counter++;
        }
    }
    while(cin>>n>>m,n+m){
        vi v;
        int temp;
        flag=false;
        rep(i,n){cin>>temp; v.push_back(temp);}
        for(int i=(int)m;i>=0;i--){
            if(check[i]){
                ans=i;break;}
        }
        bool array[MAX]; rep(i,MAX)array[i]=false;
        rep(i,n)array[v[i]]=true;
        for(int i=1;i<=ans;i++) {
            if(array[i])rep(j,n)if(i+v[j]<=ans)array[i+v[j]]=true;
            if(array[ans])break;
        }
        flag=array[ans];
        if(flag) cout<<ans<<endl;
        else cout<<"NA"<<endl;
    }
}

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

std::vector<bool> cul_prime(const int &n) {
	std::vector<bool> prime(n + 1, true);
	prime.at(0) = false;
	prime.at(1) = false;
	double root = sqrt(n) + 1;
	for (auto i = 2; i <= n >> 1; ++i) {
		prime.at(i << 1) = false;
	}
	for (auto i = 3; i < root; i += 2) {
		if (prime.at(i)) {
			for (auto j = 2; j <= n / i; ++j) {
				prime.at(i * j) = false;
			}
		}
	}
	return prime;
}
double sqrt(const int &n) {
	double a = n, b = 1;
	while ((a - b) * (a - b) < 0.1) {
		double min = (a + b) / 2;
		if (min * min > n) {
			a = min;
		}
		else {
			b = min;
		}
	}
	return a;
}
int main() {
	int n, x;
	std::cin >> n >> x;
	while (n != 0) {
		std::vector<bool> num(x + 1, false);
		std::vector<int> menu;
		for (auto i = 0; i < n; ++i) {
			int price;
			std::cin >> price;
			menu.push_back(price);
		}
		int max = 0;
		auto prime = cul_prime(x);
		num.at(0) = true;
		for (const auto &i : menu) {
			for (auto j = 0; j <= x - i; ++j) {
				if (num.at(j)) {
					if (j + i <= x) {
						num.at(j + i) = true;
						if (max < j + i && prime.at(j + i)) {
							max = j + i;
						}
					}
				}
			}
		}
		if (max == 0) {
			std::cout << "NA\n";
		}
		else {
			std::cout << max << "\n";
		}
		std::cin >> n >> x;
	}
	return 0;
}

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

int main()
{
  const int MAX_PRIME = 1000000+1;

  bool p[MAX_PRIME];
  memset(p, true, sizeof(p));
  p[0] = p[1] = false;
  for (int i = 2; i*i <= MAX_PRIME; ++i) {
    if (p[i]) {
      for (int j = i+i; j < MAX_PRIME; j += i)
	p[j] = false;
    }
  }

  vector<int> prime;
  for (int i = MAX_PRIME-1; i >= 0; --i) {
    if (p[i])
      prime.push_back(i);
  }

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

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

    vector<int> dp(x+1, 0);
    dp[0] = 1;
    for (int i = 0; i <= x; ++i) {
      if (!dp[i])
	continue;
      for (int j = 0; j < n; ++j) {
	if (i+foods[j] <= x)
	  dp[i+foods[j]] = 1;
      }
    }

    bool found = false;
    for (unsigned int i = 0; i < prime.size() && !found; ++i) {
      if (prime[i] <= x && dp[prime[i]]) {
	cout << prime[i] << endl;
	found = true;
      }
    }

    if (!found)
      cout << "NA" << endl;
  }
  return 0;
}

C++: #include <stdio.h>

int n,m[50];
bool prime[1000000],c[1000000];

void saiki(int total){
	int i;
	
	for( i=0 ; i<n ; i++){
		total-=m[i];
		if(c[total]==1)continue;
		if(total>=0){
			c[total]=1;
		}
		if(total<=0)continue;
		saiki(total);
	}
}











































int main(void)
{
	int i,j;
	//f
	prime[0]=1;
	prime[1]=1;
	for(i=3;i<1000000;i++){
		if(i%2==0){
			prime[i]=1;
		}
	}
	for(i=3;i<1000000;i+=2){
		if(prime[i]==0){
			for(j=(i+i);j<1000000;j+=i){
				prime[j]=1;
			}
		}
	}
	//
	while(1){
		int x;
		int flg=0;
		scanf("%d%d",&n,&x);
		if(n==0)break;
		
		for(i=0;i<n;i++){
			scanf("%d",&m[i]);
		}
		saiki(x);
		//
		for(i=0;i<x;i++){
			if(c[i]==1 && prime[x-i]==0){
				flg=1;
				break;
			}
		}
		if(flg==1){
			printf("%d\n",x-i);
		}
		else puts("NA");
		for(i=0;i<1000000;i++){
			c[i]=0;
		}
		for(i=0;i<50;i++){
			m[i]=0;
		}
		//
	}
	
	return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999


bool era[10000100]={false};


void makeERA(){
    for(int i=2;i<10000001;i++){
        if(era[i]==true){
            int x=10000000/i;
            for(int j=2;j<=x;j++){
                era[i*j]=false;
            }
        }
    }
    era[2]=true;
}


int main(){
    for(int i=0;i<10000101;i++)era[i]=true;
    era[0]=false;era[1]=false;
    makeERA();

    int n,x;
    while(cin>>n>>x){
        if(n==0&&x==0)break;
        vector<int> data(n);
        rep(i,n) cin>>data[i];
        
        bool dp[1000100]={};
        dp[0] = true;
        
        rep(i,n){
            int val = data[i];
            rep(j,x+1){
                if(j-val>=0) dp[j] |= dp[j-val];
            }
        }
        for(int i=x;i>=0;i--){
            if(era[i]&&dp[i]){
                cout<<i<<endl;
                goto next;
            }
        }
        cout<<"NA"<<endl;
    next:;
    }
}