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>

#define MAX 1000001

bool is_prime[MAX];
bool is_pay[MAX];

int main(int argc,char* argv[]){
  is_prime[0] = is_prime[1] = false;
  for(int i = 2; i < MAX; i++){
    is_prime[i] = true;
  }
  for(int i = 2; i < 1001; i++){
    if(is_prime[i]){
      for(int j = 2*i; j < MAX; j += i){
	is_prime[j] = false;
      }
    }
  }
  
  while(true){
    int n,x;
    std::cin >> n >> x;
    
    if(n == 0 && x == 0){
      break;
    }
    
    for(int i = 1; i <= x; i++){
      is_pay[i] = false;
    }

    is_pay[0] = true;
    
    int array[n];
    for(int i = 0; i < n; i++){
      std::cin >> array[i];
    }
    
    for(int t = 0; t < n; t++){
      for(int i = x; i >= 0; i--){
	if(is_pay[i]){
	  for(int j = i + array[t]; j <= x; j += array[t]){
	    is_pay[j] = true;
	  }
	}
      }
    }

    bool found = false;
    for(int i = x; i >= 0; i--){
      if(is_pay[i] && is_prime[i]){
	found = true;
	std::cout << i << std::endl;
	break;
      }
    }

    if(!found){
      std::cout << "NA" << std::endl;
    }
  }


  return 0;
  
}

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

const int Max = 1000001;

int dishes[31];
bool dish[Max];
bool isPrime[Max];

int main(){

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

	int n, x;
	while (std::cin >> n, n){

		std::cin >> x;
		memset(dish, 0, sizeof(dish));

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

		dish[0] = true;
		for (int i = 0; i < x; i++){
			if (dish[i]){
				for (int j = 0; j < n; j++){
					dish[i + dishes[j]] = true;
				}
			}
		}

		for (int i = x; i >= 0; i--){
			if (dish[i] && isPrime[i]){
				std::cout << i << std::endl;
				break;
			}
			if (i == 0)std::cout << "NA" << std::endl;
		}
	}

	return 0;
}

C++: #include <iostream>
using namespace std;
bool dp[1000010];
int menu[30];
int main()
{
    while(1)
    {
        int n,x;
        cin>>n>>x;if(!n)return 0;
        for(int i=0;i<n;++i){
            cin>>menu[i];
        }
        fill(dp,dp+1000010,false);
        dp[0]=true;
        for(int i=0;i<=x;++i){
            if(dp[i]){
                for(int j=0;j<n;++j){
                    dp[i+menu[j]]=true;
                }
            }
        }
        int m=0;
        for(int i=x;i>=0;--i){
            bool flag=true;
            if(dp[i]){
                for(int j=2;j*j<=i;++j){
                    if(!(i%j)){
                        flag=false;
                    }
                }
                if(flag){
                    m=i;
                    break;
                }
            }
        }
        if(m)cout<<m<<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 && i - menu[j] >= 0; j++) {
                if(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<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[31];
char memo[1000001];
char sosu[1000001];

int N(int val){
	if(val<0){
		return 0;
	}
	
	if(val==0){
		return 1;
	}
	
	if(memo[val]!=-1){
		return memo[val];
	}
	
	int ga=0;
	rep(i,n){
		if(N(val-sina[i])==1){
			ga=1;
			break;
		}
	}
	
	return memo[val]=ga;
}

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++: // 0202_AtBosssExpense.cpp
//
#include <bits/stdc++.h>
using namespace std;
const int MAX_X = 1000001;
const int MAX_N =30;
bool prime[MAX_X], dp[MAX_X];
int v[MAX_N];
int n, x;
void table() {
  fill(prime,prime+MAX_X,1);

  for(int i=2;i*i<MAX_X;++i)
    if(prime[i])
      for(int j=i*i;j<MAX_X;j+=i)
        prime[j]=0;
}
void solve() {
  fill(dp,dp+MAX_X,0);
  dp[0]=1;
  for(int i=0;i<=x;++i)
    for(int j=0;j<n;++j)
      //if(v[j]<=i&&dp[i-v[j]]) dp[i]=1;
      if(i+v[j]<=x&&dp[i]) dp[i+v[j]]=1;

  for(int i=x;i>0;--i) {
    if(prime[i]&&dp[i]) {
      cout << i << endl;
      return;
    }
  }
  cout << "NA" << endl;
}
int main() {
  table();
  while(cin >> n >> x && n && x) {
    for(int i=0;i<n;++i) cin >> v[i];
    solve();
  }
  return 0;
}

C++: #include<stdio.h>
int hideo[1000001] = { 0 };
int main(void)
{
	int  n, x, temp = 1,noyori=0,debu=0 , ruio[31] = { 0 };
	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 (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;
}