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<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++){
				if(i+List[j]<=n){
				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<iostream>
#include<vector>
using namespace std;
#define MAX 1000000
int main()
{
  int b[MAX+1]={0},i,j;
  b[0]=b[1]=1;
  for(i=4;i<=MAX;i+=2)b[i]=1;
  for(i=3;i*i<=MAX;i+=2)
    if(!b[i])for(j=i+i;j<=MAX;j+=i)b[j]=1;
  int n,x;
  bool f;
  vector<int> price;
  vector<bool> dp;
  while(cin>>n>>x,n|x){
    price.resize(n);
    for(i=0;i<n;i++)cin>>price[i];
    dp.resize(x+1);
    for(i=0;i<x+1;i++)dp[i]=(i==0);
    for(i=0;i<x+1;i++){
      if(!dp[i])continue;
      for(j=0;j<n;j++)if(i+price[j]<x+1)dp[i+price[j]]=true;
    }
    f=false;
    for(i=x;i>0;i--)if(dp[i]&!b[i]){f=true;break;}
    if(f)cout<<i<<endl;
    else puts("NA");
  }
}

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

#define rep(i, n) for (int i = 0; i < n; i++)

bool course[1000001];

bool is_prime(int n) {
    if (n % 2 == 0) return false;
    for (int i = 3; i <= std::sqrt(n); i += 2)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n, x;
    while (std::cin >> n >> x && n > 0 && x > 0) {
        rep(i, x + 1) course[i] = false;

        int prices[n];
        rep(i, n) { std::cin >> prices[i]; }
        course[0] = true;

        int max = -1;
        rep(i, x + 1) rep(j, n) {
            if (i - prices[j] >= 0 && course[i - prices[j]]) {
                if (is_prime(i)) max = i;
                course[i] = true;
                break;
            }
        }
        if (max < 0)
            std::cout << "NA" << std::endl;
        else
            std::cout << max << std::endl;
    }
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count etc.
#include <cstdlib>	// require abs
#include <cstdio>	// require printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen

using namespace std;

const int MAX_N = 1000000;
bool prime[MAX_N+1];

void make_prime (void )
{
	fill (prime, prime + MAX_N, true );

	prime[0] = false;
	prime[1] = false;

	for (int i = 2; i < MAX_N + 1; ++i ){
		if (prime[i] ){
			for (int j = 2*i; j < MAX_N + 1; j += i ){
				prime[j] = false;
			} // end for
		} // end if
	} // end for
}

bool dp[MAX_N+1];

int main()
{
//	cut here before submit 
//	freopen ("testcase.be", "r", stdin );
	int n, x;

	make_prime ();

	while (cin >> n >> x && n && x ){
		vector <int> cost (n, 0 );
		for (int i = 0; i < n; ++i ){
			cin >> cost[i];
		} // end for
		memset (dp, false , sizeof (dp ) );

		dp[0] = true;
		for (int i = 0; i < n; ++i ){
			for (int j = cost[i]; j <= x; ++j ){
				dp[j] |= dp[j - cost[i]];
			} // end if
		} // end for

		int res = 0;
		for (int j = MAX_N; j >= 0; --j ){
			if (dp[j] && prime[j] ){
				res = j;
				break;
			} // end if
		} // end for

		if (res == 0 ){
			cout << "NA" << endl;
		}else{
			cout << res << endl;
		} // end if
	} // end loop
		
	return 0;
}

C++: #include <cstdio>
#include <cstring>
bool dp[1000001],prime[1000001];
int main() {
	for(int i=2;i*i<=1000000;i++) {
		if(!prime[i]) for(int j=i*2;j<=1000000;j+=i) prime[j]=true;
	}
	int n,x,cook[30];
	while(scanf("%d %d",&n,&x),n) {
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++) {
			scanf("%d",&cook[i]);
		}
		dp[0]=true;
		for(int i=0;i<n;i++) {
			for(int j=1;j<=x;j++) {
				if(j>=cook[i]) dp[j]|=dp[j-cook[i]];
			}
		}
		bool NA=true;
		for(int i=x;i>0;i--) {
			if(!prime[i]&&dp[i]) {
				NA=false;
				printf("%d\n",i);
				break;
			}
		}
		if(NA) printf("NA\n");
	}
}

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

#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int n,m;
int sina[301];
char memo[1000002];
char sosu[1000002];
char roop[1000002];

char N(int val){
	printf("%d\n",val);
	if(val<0 || val>1000000){
		return 0;
	}
	
	if(val==0){
		return 1;
	}
	
	if(memo[val]!=-1){
		return memo[val];
	}
	
	for(roop[val]=0; roop[val]<n; ++roop[val]){
		if(N(val-sina[roop[val]])==1){
			return memo[val] = 1;
		}
	}
	
	return memo[val]=0;
}

int main(){
	sosu[0]=1;sosu[1]=1;
	for(int i=2;i<1000001;i++){
		if(sosu[i]==1){
			continue;
		}
		for(int j=i*2;j<1000001;j+=i){
			sosu[j]=1;
		}
	}
	
	while(1){
		sintt(n,m);
		if(n==0)break;
		rep(i,n){
			sint(sina[i]);
		}
		
		rep(i,1000001){
			memo[i]=-1;
		}
		
		int flg=1;
		int ans=0;
		
		
		for(int i=m;i>0;i--){
			if(sosu[i]!=0){
				continue;
			}
			
			if(N(i)==1){
				ans=i;
				flg=0;
				break;
			}
		}
		
		/*
		rep(i,m){
			if(memo[i]==0){
				printf("%d\n",i);
			}
		}*/
		
		if(flg==1){
			puts("NA");
		}else{
			printf("%d\n",ans);
		}
	}
}

C++: #include <iostream>
#include <cstdio>
using namespace std;
#define sosu 1000001
bool so[sosu];
int n,x,c[31];
bool his[sosu];
int ans;

void hantei() {
  so[0] = so[1] = 1;
  for(int i=2;i*i<=sosu;i++) 
    if(so[i] == 0) 
      for(int j=2;j<=sosu/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;i++) his[i] = 0;
    
    ans = -1;
    saiki(0);
    
    if(ans == -1) cout <<"NA"<<endl;
    else cout << ans << endl;
    
  }
  return 0;
}