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 <map>
#include <string>

using namespace std;

int dp[1000001];
int kind[31];


const int MAX_SIZE = 10000;
const int MAX_PRIME = 1000000;


int prime[MAX_PRIME+1];
bool isPrime[MAX_PRIME+1];
int p;

void erats(){
	// primeXgðú»
	fill(isPrime,isPrime+MAX_PRIME,true);
	p = 0;
	isPrime[0] = isPrime[1] = false;

	for(int i = 2; i <= MAX_PRIME; i++){
		if(isPrime[i]){
			prime[p++] = i;
		}
		else
			continue;

		// Óé¢É©¯é
		for(int j = 2*i; j <= MAX_PRIME; j+=i){
			isPrime[j] = false;
		}
	}
}


int main(){

	int n;
	int x;
	erats();
	while(cin>>n>>x&&!(n==0&&x==0)){
		for(int i = 0; i < n; i++){
			cin>>kind[i];
		}
		// eàzÌ¥¢ûª½íÞ é©ðßé
		dp[0]=1;
		int maxCost=-1;

		for(int i = 1; i <= x; i++){
			dp[i]=0;
			for(int j = 0; j < n; j++){
				if(i-kind[j]>=0){
					dp[i]+=dp[i-kind[j]];
				}
			}
			if(dp[i]>=1&&(isPrime[i]||i==1||i==0)){
				maxCost=max(i,maxCost);
			}
		}


		if(maxCost==-1)
			cout<<"NA"<<endl;
		else
			cout<<maxCost<<endl;
	}

	return 0;
}

C++: #include<stdio.h>
#include<string.h>
int hideo[1000001] = { 0 };
int noyori = 0, debu = 0, n, x, temp = 1, ruio[31] = { 0 };
int main(void)
{
	while (scanf("%d %d", &n, &x)) {
		if (n == 0 && x == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ruio[i]);
			hideo[ruio[i]] = 1;
		}
		while (temp != x) {
			if (hideo[temp] == 1) {
				for (int j = 1; j <= n; j++) {
					if (temp + ruio[j] > x)continue;
					if (hideo[temp + ruio[j]] == 0) {
						hideo[temp + ruio[j]] = 1;
					}
				}
			}
			temp++;
		}
		for (int i = x; i >= 1; i--) {
			if (hideo[i] == 1) {
				for (int j = 2; j < i - 1; j++) {
					if (i%j == 0) {
						debu = 1;
					}
				}
				if (debu == 0) {
					noyori = i;
					break;
				}
			}
			debu = 0;
		}
		if (noyori > 1) {
			printf("%d\n", noyori);
		}
		else {
			printf("NA\n");
		}
		temp = 1;
		noyori = 0;
		debu = 0;
		for (int i = 1; i <= n; i++) {
			ruio[i] = 0;
		}
		for (int i = 1; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

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

constexpr int MAX_N = 30, MAX_C = 1000001;
int n, max;
int cost[MAX_N];
int dp[MAX_C];
bool prime_num[MAX_C];

int main() {
	while (1) {
		std::cin >> n >> max;
		if (n + max == 0)
			break;
		std::memset(prime_num, false, sizeof(prime_num));
		std::memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; ++i)
			std::cin >> cost[i];
		for (int i = 2; i * i <= max; ++i) {
			if (!prime_num[i]) {
				for (int j = 2; i*j <= max; ++j)
					prime_num[i*(j + 2)] = true;
			}
		}
		int ans = 0;
		for (int i = 1; i <= max; ++i) {
			dp[i] = dp[i - 1];
			for (int j = 0; j < n; ++j) {
				if (i >= cost[j]) {
					if (!prime_num[dp[i - cost[j]] + cost[j]])
						ans = dp[i - cost[j]] + cost[j];
					dp[i] = std::max(dp[i], dp[i - cost[j]] + cost[j]);
				}
			}
		}
		if (!ans)
			std::cout << "NA" << std::endl;
		else
			std::cout << ans << std::endl;
	}
	return 0;
}

C++: #include<iostream>
#define N 1000001
using namespace std;
int main(){
  int p[N]={0};
  for(int i=3;i<N;i+=2) p[i] = 1;
  p[2] = 1;
  for(int i=3;i<=1000;i+=2){
    if(p[i]==1){
      for(int j=2*i;j<N;j+=i) p[j] = 0;
    }
  }
  int n,x;
  while(cin >> n >> x){
    if(n==0&&x==0) break;
    int t[x+1];
    for(int i=0;i<=x;i++) t[i] = 0;
    for(int i=0;i<n;i++){
      int k;
      cin >> k;
      if(k<=x) t[k] = 1;
      for(int j=1;j<=x;j++){
    if(t[j]==1&&j+k<=x) t[j+k] = 1;
      }
    }
    bool ok = false;
    for(int i=x;i>=0;i--){
      if(t[i]==1&&p[i]==1){
    cout << i << endl;
    ok = true;
    break;
      }
    }
    if(!ok) cout << "NA" << endl;
  }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstring>
#define SIZE 1000000
using namespace std;

bool data[SIZE];
int d[99];
int n, x;
bool memo[SIZE];
int ans;

bool solve(int s){

  if(s > x) return 0;
  if(memo[s]) return true;

  for(int i=0;i<n;i++){
    solve(s+d[i]);
    if(data[s]) ans = max(ans, s);
  }

  memo[s] = true;
  return true;
}

int main(){

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

  while(true){
    cin >> n >> x;
    if(!n && !x) break;

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

    memset(memo, false, sizeof(memo));
    
    ans = 0;
    solve(0);
    if(ans) cout << ans;
    else cout << "NA";
    cout << endl;
  }
}

C++: #include<iostream>
#include <cstdio>
#include<string>
#include<math.h>
using namespace std;
//int ha(string);
//int saga(int);
int q,m,n=1000000,List[1000];
bool  slist[1000001];
bool  klist[1000001];

int main()
{	
	int i,j,k,b=0,s,a=2,f=0,c=0;
	for( i = 0; i <n;i++ ){
		slist[i]=true;
		klist[i]=false;
	}

	i=0;
	while(i<sqrt((double)n)){
		for(i=a+a;i<n;i=i+a){
			slist[i]=false;
		}
		for(i=a+1;i<sqrt((double)n);i++){
			if(slist[i]==true){
				a=i;
				break;
			}
		}
	}
	cin>>m>>n;
	while(m!=0||n!=0){
	for( i = 0; i <n;i++ ){
		klist[i]=false;
	}
	for(i=0;i<m;i++){
		cin>>List[i];
		klist[List[i]]=true;
	}
		for(i=0;i<n;i++){
			if(klist[i]){
			for(j=0;j<m;j++){				
				klist[i+List[j]]=true;
			}
		}
	}
		for(i=n;i>0;i--){
			if(klist[i]&&slist[i]){
			break;
		}
	}
		if(i==0){
			printf("NA\n");
		}
		else{
		printf("%d\n",i);
		}
		cin>>m>>n;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
vector <bool> sosu(1000010,true);
void a(){
	sosu[1] = false;
	for(int i = 2; i < 1000010; i++){
		if(sosu[i] == true)
			for(int j = 2; i*j < 1000010; j++){
				sosu[i * j] = false;
			}
	}
}

int main(){
	int n,x;
	a();
	while(cin >> n >> x, n){
		bool dp[1000010] = {0};
		dp[0] = true;
		int v[n];
		for(int i = 0; i < n; i++)
			cin >> v[i];
		sort(v,v + n);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < 1000010; j++){
				if(dp[j] == true && j + v[i] < 1000010)
					dp[j + v[i]] = true;
					
			}
		}
		int judge = true;
		for(int i = x; i != 1; i--)
			if(dp[i] == true && sosu[i] == true){
				cout << i << endl;
				judge = false;
				break;
			}
		if(judge)
			cout << "NA" << endl;
	}
	return 0;
}