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 <algorithm>
#include <cstring>
using namespace std;
const int XMAX = 1000000;
constexpr int SQRTXMAX = sqrt(XMAX);

bool is_prime[XMAX + 1];
bool dp[XMAX + 1];
int cost[30];

int main() {
  // prime
  memset(is_prime, true, sizeof(is_prime));
  is_prime[0] = is_prime[1] = false
  for (int i = 2; i <= SQRTXMAX) {
    if (is_prime[i]) {
      int current = i * i;
      for (int j = i * i; j <= XMAX; j += i) {
        is_prime[j] = false;
      }
    }
  }

  int n, x;
  while (cin >> n >> x, n) {
    for (int i = 0; i < n; i++) cin >> cost[i];

    // dp
    r = 0;
    dp[0] = true;
    for (int i = 1; i <= x; i++) {
      for (int j = 0; j < n; j++) {
        int k = i - cost[j];
        if (k >= 0 && dp[k]) {
          dp[i] = true;
          if (is_prime[i]) r = i;
          break;
        }
      }
    }

    if (r == 0) {
      cout << "NA" << endl;
    } else {
      cout << r << endl;
    }
  }
  return 0;
}

C++: #include<stdio.h>
#include <string.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[1000002]={0};
int main()
{
	scanf("%d %d",&n,&p);
	while(1){
		//memset(youso, 0, sizeof(youso));
	
		if(n==0&&p==0){
			break;
		}
		for(cnt=1;cnt<=n;cnt++){
			scanf("%d",&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;
		
		scanf("%d %d",&n,&p);
			for(int i=0;i<p+1;i++){
			youso[i]=0;
		}
	}
	return 0;
}

C++: #include<iostream>

using namespace std;

bool pri[1000001];
int price[31];
int n,x;
int dp[1000001];
int dps(int i,int sum_m){
  int ss=0;
  int ans;
  if(dp[sum_m]!=-1)
    {
      return dp[sum_m];
    }
  if(i>=n)
    return 0;
  if(sum_m>=x)
    return 0;
  //  cout<<sum_m<<endl;
  if(pri[price[i]+sum_m] && ans<price[i]+sum_m &&sum_m+price[i]<=x)
    {
      ans=price[i]+sum_m;
      if(ss<ans)
	ss=ans;
    }
  ans= dps(i,price[i]+sum_m);
  if(ss<ans)
    ss=ans;
  ans = dps(i+1,sum_m);
  if(ss<ans)
    ss=ans;
  dps(i+1,sum_m+price[i]);
  if(ss<ans)
    ss=ans;
  
  dp[sum_m]=ss;
  //  cout<<ss<<endl;
  return ss;
}

int main()
{
  int ans;
  fill(pri,pri+1000001,true);
  for(int i=2;i<1000001/2;i++)
    {
      for(int x=i+i;x<1000001;x+=i)
	pri[x]=false;
    }
  for(;cin>>n>>x,n;)
    {
      for(int i=0;i<n;i++)
	{
	  cin>>price[i];
	}
	for(int j=0;j<1000001;j++)
      	  dp[j]=-1; 
      ans=dps(0,0);
      if(ans==0)
	cout<<"NA"<<endl;
      else
	cout<<ans<<endl;
    }
}

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

const int MAX = 1000000;
char p[MAX+1] = {0};
int a[31];
int n,x,ans;

void solve(int sum){
	if( sum > x ) return;
	if( p[sum] ) ans = max( ans , sum );

	for(int i=0 ; i < n ; i++ ){
		solve( sum+a[i] );
	}
}

int main(){
	for(int i=2 ; i < MAX+1 ; i++ ) p[i] = 1;
	for(int i=2 ; i*i < MAX+1 ; i++ ){
		if( p[i] ){
			for(int j=i+i ; j < MAX+1 ; j += i ){
				p[j] = 0;
			}
		}
	}

	while( cin >> n >> x , n||x ){
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		ans = 0;
		solve( 0 );
		if( ans > 0 )
			cout << ans << endl;
		else
			cout << "NA" << endl;
	}
}

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

const int MAX_X = 1000000, MAX_N = 30;
int n,x;
bool is_prime[MAX_X+1];
int menu[MAX_N];

void sieve()
{
    fill(is_prime, is_prime + MAX_X + 1, false);
    is_prime[2] = true;
    for(int i = 3; i <= MAX_X; i+=2) {
        is_prime[i] = true;
        for(int j = 3; j * j <= i; j+=2) {
            if(!(i % j)) {
                is_prime[i] = false;
                break;
            }
        }
    }
}

int main()
{
    sieve();
    while(cin >> n >> x && n) {
        for(int i = 0; i < n; i++) 
            cin >> menu[i];
        
        bool price[x + 1];
        fill(price, price + x + 1, false);
        price[0] = true;
        int max = -1;
        for(int i = 1; i <= x; i++) {
            for(int j = 0; j < n; j++) {
                if(i - menu[j] >= 0 && price[i - menu[j]]) {
                    price[i] = true;
                    if(is_prime[i]) 
                        max = i;
                }
            }
        }
        if(max < 0) 
            cout << "NA" << endl;
        else 
            cout << max << endl;
    }
}

C++: #include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))
#define X 1000001
int ans;
int n,x;
bool p[X];
char dp[2*X];

int main(){
	p[0]=1;
	reps(i,2,X)if(!p[i])for(int j=i+i;j<X;j+=i)p[j]=1;
	for(;;){
		scanf("%d%d",&n,&x);
		if(!n)break;
		x++;
		vector<int> v(n);
		rep(i,n){
			cin >> v[i];
		}
		fill_n(dp,X,0);
		dp[0]=1;
		ans=0;
		rep(i,n){
			rep(j,x){
				if(dp[j] && j+v[i]<x){
					dp[j+v[i]]=1;
					if(!p[j+v[i]])ans = max(ans,j+v[i]);
				}
			}
		}
		if(ans)printf("%d\n",ans);
		else puts("NA");

	}
	return 0;
}

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

using namespace std;

int main()
{
	static bool era[1000000];
	for(int i=1;i<1000000;i++)	era[i]=true;
	for(int i=2;i<1000;i++){
		if(era[i])	for(int j=i*i;j<1000000;j+=i)	era[j]=false;
	}

	for(int n,bud;scanf("%d%d",&n,&bud),n;){
		int menu[30];
		for(int i=0;i<n;i++)	scanf("%d",menu+i);

		static bool knap[1000001];
		knap[0]=true;
		for(int i=1;i<=bud;i++)	knap[i]=false;
		for(int i=0;i<n;i++){
			for(int j=0;j<bud;j++){
				if(knap[j] && j+menu[i]<=bud)
					knap[j+menu[i]]=true;
			}
		}

		bool b=false;
		for(int i=bud;i>=0;i--){
			if(knap[i] && era[i]){
				printf("%d\n",i);
				b=true;
				break;
			}
		}
		if(!b)	puts("NA");
	}

	return 0;
}