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<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define INF (1111111)
int N,X;
int r[31];
bool sosu[1000001];
int dp[1000001];
int solve(int sum){
  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;
  }  
}
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]);
    }
    int res = solve(0);
    if(res==0) puts("NA");
    else printf("%d\n",res);
  }
}

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

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;
}
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;
}
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 <bits/stdc++.h>
using namespace std;
bool e[1000001],dp[1001110];
int 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 <iostream>
#include <cstdio>
using namespace std;
#define sosu 1000000
bool so[2000001];
int n,x,c[31];
bool his[2000001];
int ans;

void hantei() {
  so[0] = so[1] = 1;
  for(int i=2;i*i<=1000001;i++) 
    if(so[i] == 0) 
      for(int j=2;j<=1000001/i;j++)so[i*j] = 1;
}


void saiki(int sum) {
  his[sum] = 1;
  if(so[sum] == 0 && ans < sum) ans = sum;
  
  for(int i=0;i<n;i++) 
    if(c[i]+sum <= x && his[c[i]+sum] == 0) 
      saiki(c[i]+sum);
}


int main() {
  hantei();

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

    
    for(int i=0;i<n;i++) cin >> c[i];
    for(int i=0;i<=x+1;i++) his[i] = 0;
    cout << "NA"<<endl;
    continue;
    
    ans = -1;
    saiki(0);
    
    if(ans == -1) cout <<"NA"<<endl;
    else cout << ans << endl;
    
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
int n, x;
int v[30], dp[30][1000001], rsk[30][1000001];
bool sosu[1000001];
int main()
{
	for(int i = 2; i < 1000000; i++)
	{
		if(!sosu[i])
		{
			for(int j = 2; j * i <= 1000000; j++)
			{
				sosu[i * j] = 1;
			}
		}
	}
	while(1)
	{
		cin >> n >> x;
		if(n == 0 && x == 0)
			break;
		for(int i = 0; i < n; i++)
		{
			cin >> v[i];
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;

		for(int i = 0; i < n - 1; i++)
			for(int j  = 0; j <= x; j++)
				if(dp[i][j])
					for(int k = 0; j + k * v[i] <= x; k++)
						dp[i + 1][j + k * v[i]] = dp[i][j];

					for(int i = x; i >= 0; i--)
					{
						if(!sosu[i] && dp[n - 1][i])
						{
							if(i)
								cout << i << endl;
							else
								cout << "NA" << endl;
							break;
						}
					}
				}
				return 0;
			}

C++: #include <iostream>
#include <algorithm>
#include <limits>
#include <cstring>

constexpr int MAX_X = 1000001;
constexpr int MAX_N = 31;

int n, x, values[MAX_N];
bool is_prime_number[MAX_X] = {true};

void initialize();

void solve();

int main(){
   initialize();
   while(true){
       memset(values, 0, MAX_N);

       std::cin >> n >> x;
       
       if(n + x == 0) break;
       
       for(int i = 0; i < n; ++i)
           std::cin >> values[i];

       solve();
   }
   return 0;
}

void initialize(){
    memset(is_prime_number, true, MAX_X);
    is_prime_number[0] = false, is_prime_number[1] = false;
    for(int i = 2; i <= 1000; ++i){
        if(is_prime_number[i]){
            for(int j = i + 1; j < MAX_X; ++j){
                if(j % i == 0)
                    is_prime_number[j] = false;
            }
        }
    }
}

void solve(){
   int ans = 0;
   int dp[MAX_X];
   memset(dp, 0, MAX_X);

   /*
   std::cout << "x : " << x << std::endl << "n : " << n << std::endl;
   for(int i = 0; i < (x > 1000 ? 1000 : x); ++i){
       std::cout << i << " dp : " << dp[i] << std::endl;
   }
   */

   for(int i = 1; i <= x; ++i){
       int res = 0;
       for(int j = 0; j < n; ++j){
           if(values[j] <= i){
               res = std::max(dp[i - values[j]] + values[j], res);
           }
       }
       dp[i] = std::max(dp[i], res);
       if(is_prime_number[dp[i]]){
           ans = std::max(dp[i], ans);
       }
   }

   if(ans != 0){
       std::cout << ans << std::endl;
   }
   else{
       std::cout << "NA" << std::endl;
   }

}