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++: import java.util.*;

class Main {

    static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {

        while (scan.hasNext()) {
            int n = scan.nextInt();
            int money = scan.nextInt();
            boolean[] dp = new boolean[money+1];
            if (n == 0) {
                break;
            }
            int[] menu = new int[30];
            for (int i = 0; i < n; i++) {
                menu[i] = scan.nextInt();
            }
            solve(dp, menu);
            int i;
            for (i = dp.length-1; i >= 0; i--) {
                if (dp[i] && prime(i)) {
                    break;
                }
            }
            if (i < 0) {
                System.out.println("NA");
            } else {
                System.out.println(i);
            }
        }
    }

    public static void solve(boolean dp[], int menu[]) {
        for (int i = 0; i < menu.length; i++) {
            if (menu[i] > dp.length) {
                continue;
            }
            dp[menu[i]] = true;
            for (int j = 1; j < dp.length; j++) {
                if (dp[j] && j + menu[i] < dp.length) {
                    dp[j+menu[i]] = true;
                }
            }
        }
    }



    public static boolean prime(int a) {
        if (a <= 3) {
            return true;
        } else {
            for (int i = 2; i * i <= a; i++) {
                if (a % i == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

C++: #include<iostream>
using namespace std;
#define MAX_N 1000010
bool prime[MAX_N], dp[MAX_N];
int main(){
	for(int i=0;i<=MAX_N;i++){
		prime[i] = true;
	}
	prime[0] = prime[1] = false;
	for(int i=2;i*i<MAX_N;i++){
		if(prime[i]){
			for(int j=i*2;j<=MAX_N;j+=i)prime[j] = false;
		}
	}

	int n, x, menu[30];
	while(1){
                cin >> n >> x;
                if(n==0&&x==0)break;
		for(int i=0;i<=x;i++){
			dp[i] = false;
		}

		for(int i=0;i<n;i++){
			cin >> menu[i];
		}

		int res = 0;

		dp[0] = true;
		for(int i=1;i<=x;i++){
			for(int j=0;j<n;j++){
				if(i-menu[j] >= 0 && dp[i-menu[j]]){
					dp[i] = true;
					break;
				}
			}
			if(dp[i] && prime[i]){
				res = i;
			}
		}

		if(res != 0){
			cout << res << endl;
		}else{
			cout << "NA" << endl;
		}
	}
}

C++: #include <bits/stdc++.h>
#define int long long
using namespace std;
bool e[1000001],dp[1001110];
main(){
  e[0]=e[1]=1;
  for(int i=2;i<1000001;i++)
    for(int j=i*2;j<1000001;j+=i)
      e[j]=1;
  int n,m;
  while(cin>>n>>m,n){
    for(int i=0;i<m+110;i++)dp[i]=0;
    int a[n],c=1,p;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
      for(int j=1;j<=m;j++){
        if(dp[j]&&a[i]+j<=m)dp[a[i]+j]=1;
        if(a[i]*j<=m)dp[a[i]*j]=1;}
    for(p=m;p>=0;p--)if(dp[p]&&!e[p]){c=0;break;}
    if(c)cout<<"NA"<<endl;
  else cout<<p<<endl;
  }
}

C++: #include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
bool sosu(int n) {
  if (n <= 1)
    return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0)
      return false;
  return true;
}
int main() {
  int n, x;
  while (cin >> n >> x, n) {
    bool dp[1000001] = {};
    dp[0] = 1;
    int a[50];
    rep(i, n) { cin >> a[i]; }
    rep(i, n) rep(j, x) {
      if (dp[j])
        dp[j + a[i]] = 1;
    }
    for (int i = x; i > 1; i--) {
      if (dp[i])
        if (sosu(i)) {
          cout << i << endl;
          goto end;
        }
    }
    cout << "NA" << endl;
  end:;
  }
  return 0;
}

C++:  #include<cstdio>
#include<iostream>
using namespace std;
int main(){
	bool prime[1000000];
	prime[1] = true;
	for(int i = 2; i * i <= 1000000; i++){
		if(!prime[i]){
			for(int j = i * i; j <= 1000000; j += i){
				prime[j] = true;
			}
		}
	}
	int n,w;
	while(cin >> n >> w){
		if(n == 0 && w == 0) break;
		bool dp[1000001] = {0};
		int data[31];
		for(int i = 0; i < n; i++){
			cin >> data[i];
		}
		dp[0] = true;
		for(int i = 0; i < n; i++){
			for(int j = data[i]; j <= w; j++){
				if(dp[j - data[i]]){
					dp[j] = true;
				}
			}
		}
		int ans = 0;
		for(int i = w; i >= 2; i--){
			if(!prime[i] && dp[i]){
				ans = i;
				break;
			}
		}
		if(ans == 0)puts("NA");
		else printf("%d\n",ans);
	}
	return 0;
}

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

#define MAXNUM 1000001

bool prime[MAXNUM];
bool price[MAXNUM];

int main()
{
	prime[0]=prime[1]=false;
	for(int i=2; i<MAXNUM; i++)
	{
		prime[i]=true;
	}
	
	for(int i=2; i*i<MAXNUM; i++)
	{
		if(prime[i])
		{
			for(int j=i*i; j<MAXNUM; j+=i)
			{
				prime[j]=false;
			}
		}
	}

	int n,x,p;
	while(cin >> n >> x, (n||x))
	{
		price[0] = true;
		for(int i=1; i<=x; i++)
		price[i] = false;

		while(n--)
		{
			cin >> p;
			for(int i=p; i<=x; i++)
			{
				if(price[i-p]) price[i]=true;
			}
		}

		int j;
		for(j=x; j>1; j--)
		{
			if(price[j]&&prime[j])
			{
				cout << j << endl;
				break;
			}
		}
		if(j==1) cout << "NA" << endl;
	}
}

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

using namespace std;
const int MAX = 1000000;
vector<int> Primes;
bool isPrime[MAX] = {0};

void sieve(){
    bool find[MAX] = {0};
    int i;
    for(i=2;i*i < MAX;i++){
        if(find[i]) continue;
        Primes.push_back(i);
        for(int j=i;j<MAX;j++){
            if(j%i == 0) find[j] = true;
        }
    }
    for(;i<MAX;i++){
        if(!find[i]) Primes.push_back(i);
    }
    for(int i=0;i<Primes.size();i++){
        isPrime[Primes[i]] = true;
    }
    Primes.clear();
}

int main(){
    sieve();

    while(true){
        int n,x;
        cin >> n >> x;
        if(n==0 && x==0) return 0;
        vector<int> R(n);
        for(int i=0;i<n;i++){
            cin >> R[i];
        }

        set<int> S;
        S.insert(0);
        for(int i=0;i<R.size();i++){
            for(set<int>::iterator it=S.begin();it!=S.end();++it){
                int newe = *it + R[i];
                if(newe > x) continue;
                S.insert(newe);
            }
        }
        int maxn = -1;
        for(set<int>::iterator it=S.begin();it!=S.end();++it){
            if(isPrime[*it] && *it > maxn) maxn = *it;
        }
        if(maxn == -1) cout << "NA" << endl;
        else cout << maxn << endl;
    }
    return 0;
}