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 <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;
 
typedef ostringstream OSS;
typedef istringstream ISS;
 
typedef vector<int> VI;
typedef vector< VI > VVI;
 
typedef long long LL;
 
typedef pair<int, int> PII;
typedef vector<PII> VPII;
 
#define X first
#define Y second

vector<bool> Prime;
void initPrime(long num) {
	Prime = vector<bool>(num + 1, true);
	Prime[1] = Prime[0] = false;
	for (long i = 2; i * i <= num; i++) {
		if (Prime[i]) {
			for (long j = i + i; j <= num; j += i) {
				Prime[j] = false;
			}
		}
	}
}
 
int main(void) {
	initPrime(1000000);
	int N, X;
	while (cin >> N >> X, N) {
		VI ps(N);
		for (auto &p : ps) cin >> p;
		
		vector<bool> dp(X + 1);
		dp[0] = true;

		for (auto p : ps) {
			for (int i = 0; i <= X; i++) {
				if (!dp[i]) continue;

				int np = i + p;
				if (np <= X) {
					dp[np] = true;
				}
			}
		}

		int ans = 0;
		for (int i = 0; i <= X; i++) {
			if (dp[i] && Prime[i]) ans = i;
		}

		if (ans) cout << ans << endl;
		else cout << "NA" << endl;
	}

}

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

constexpr int MAX_X = 1000000, MAX_N = 30;

int value[MAX_N], n, x;
bool dp[MAX_X + 1];
bool is_prime_number[MAX_X + 1];

void initialize();

void solve();

int main(){
    initialize();

    while(true){
        std::cin >> n >> x;
        if(n == 0 && x == 0){
            break;
        }
        
        memset(dp, false, x + 1);

        dp[0] = true;

        for(int i = 0; i < n; ++i){
            std::cin >> value[i];
            dp[value[i]] = true;
        }

        solve();
    }
    return 0;
}

void solve(){
    int ans = 0;

    for(int i = 2; i < x + 1; ++i){
        for(int j = 0; j < n; ++j){
            if(i >= value[j]){
                if(dp[i - value[j]]){
                    dp[i] = true;

                    if(is_prime_number[i]){
                        ans = std::max(ans, i);
                    }

                    break;
                }
            }
        }
    }

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

void initialize(){
    memset(is_prime_number, true, MAX_X + 1);

    is_prime_number[0] = false, is_prime_number[1] = false;
    for(int i = 2; i * i < MAX_X + 1; ++i){
        if(is_prime_number[i]){
            for(int j = 2; i * j < MAX_X + 1; ++j){
                is_prime_number[i * j] = false;
            }
        }
    }
}

C++: #include<iostream>
#include<queue>
#include<functional>
#include<set>
using namespace std;
int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    vector<int> menu(n);
    for(int i=0;i<n;i++){
      cin>>menu[i];
    }
    int p = -1;
    bool money[x+1];
    money[0] = true;
    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]])
	  money[i] = true;
      }
      if(money[i]&&prime[i])p=i;
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

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

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;
const double PI = acos(-1.0);
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct
{
    int to;
    int cost;
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool isPrime[1000010];
bool dp[1000010];

void Eratostenes(int N)
{
    rep(i, 1e6 + 1) isPrime[i] = true;

    isPrime[0] = false;
    isPrime[1] = false;

    for(int i = 2; i <= sqrt(N); i++)
    {
        if(isPrime[i])
        {
            for(int j = i * 2; j <= N; j += i)
                isPrime[j] = false;
        }
    }   
}

int main()
{
    int N, X;
    Eratostenes(1000000);   

    while(cin >> N >> X && N)
    {
        vector<int> v(N);
        rep(i, N) cin >> v[i];
        rep(i, X + 1) dp[i] = false;

        dp[0] = true;

        rep(i, N)
        {
            rep(j, X + 1)
            {
                if(!dp[j] || j + v[i] > X) continue;

                dp[j + v[i]] = true;
            }
        }

        int ans = 0;

        rep(i, X + 1)
        {
            if(dp[i] && isPrime[i])
                ans = max(ans, i);
        }

        cout << (ans == 0 ? "NA" : to_string(ans)) << endl;

    }

    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int sosu[1000005]={0};
int check[50][1000005];
main(){
  int n,k;
  int shop[50];
  sosu[1]=1;
  for(int i=2;i<(int)sqrt(1000005);i++){
    if(sosu[i]==0){
      for(int j=i;j<1000005;j+=i){
	sosu[j]=1;
      }
    }
  }
  while(1){
    bool a=true;
    cin>>n>>k;
    if(n==0&&k==0)break;
    memset(check,0,sizeof(check));
    for(int i=1;i<=n;i++){
      cin>>shop[i];
    }
    for(int i=1;i<=n;i++){
      for(int j=1;j<=k;j++){
	if(check[i-1][j]==1){
	  for(int l=j;l<=k;l+=shop[i]){
	    check[i][l]=1;
	  }
	}
      }  
      for(int j=shop[i];j<=k;j+=shop[i]){
	check[i][j]=1;
      }
    }
    for(int i=k;i>0;i--){
      if(sosu[i]==0&&check[n][i]==1){
	cout<<i<<endl;
	i=0;
	a=false;
      } 
    }
    if(a){
      cout<<"NA"<<endl;
    }
  }
}

C++: #include<stdio.h>
int isPrime(int x){
	int i;
	if(x<2) return 0;
	else if(x==2) return 1;
	if(x%2==0) return 0;
	for(i=3;i*i<=x;i+=2){
		if(x%i==0) return 0;
	}
	return 1;
}
int p,cnt,cnt2,food;
int n,d=0,g,kakaku[31],flag,youso[1000001]={0};
int main()
{
	scanf("%d %d",&n,&p);
	while(n!=0&&p!=0){
		for(cnt=1;cnt<=n;cnt++){
			scanf("%ld",&food);
			youso[food]=1;
			kakaku[cnt]=food;
		}
		for(cnt=0;cnt<=p;cnt++){
			if(youso[cnt]==1){
				for(cnt2=1;cnt2<=n;cnt2++){
					if(cnt+kakaku[cnt2]<=p){
						youso[cnt+kakaku[cnt2]]=1;
					}
				}
			}
		}
		flag=0;
		for(cnt=p;cnt>=0;cnt--){
			if(youso[cnt]==1){
				g=cnt;
				d=isPrime(g);
				if(d==1){
					flag=1;
					d=cnt;
					printf("%d\n",d);
					break;
				}
			}
		}
		if(flag==0){
			printf("NA\n");
		}
		d=0;
		flag=0;
		for(cnt=0;cnt<=p;cnt++){
			youso[cnt]=0;
		}
		scanf("%d %d",&n,&p);
	}
	return 0;
}