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>
#define MAX 1000000
using namespace std;

bool prime[MAX+1];

bool hurui(){
  for(int i=0;i<MAX;i++){prime[i]=true;}
  prime[0]=prime[1]=prime[2]=true;
  
  for(int i=2;i<MAX;i++){
    if(prime[i]){
      for(int j=2*i;j<MAX;j+=i)prime[j]=false;
    }
  }
}


int main(){
  hurui();
  
  for(;;){
    int n,x;
    cin >> n >> x;
    if(n==0)return 0;
    
    int kane[n];
    for(int i=0;i<n;i++)
      cin >> kane[i];
    
    bool dp[x+1];
    for(int i=0;i<=x;i++)dp[i]=false;
    dp[0]=true;
    
    for(int i=0;i<=x;i++){
      if(dp[i]){
	for(int j=0;j<n;j++){
	  if(i+kane[j]<=x)dp[i+kane[j]]=true;
	}
      }
    }

    //cout << "aa";
    for(int i=x;i>=0;i--){
      if(i==0){
	cout << "NA" << endl;
	break;
      }
      if(dp[i]&&prime[i]){
	cout << i << endl;
	break;
      }
    }
  } 
  
}

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

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
#define MOD 1e9 + 7

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;

#define MAX 1000000

bool prime[1000000];
int N, X;
int price[30];
int dp[31][1000001];

void PrimeJudge() {
	memset(prime, true, sizeof(prime));
	prime[0] = false;
	FOR(i, 1, sqrt(MAX)) {
		if(prime[i]) {
			for(int j = (i + 1); (i + 1) * j <= MAX; ++j) {
				prime[(i + 1) * j - 1] = false;
			}
		}
	}
	return;
}

int main() {
	PrimeJudge();
	while(scanf("%d %d", &N, &X), N || X) {
		rep(i, N) scanf("%d", &price[i]);
		rep(i, N) rep(j, X + 1) {
			if(j < price[i]) {
				dp[i + 1][j] = dp[i][j];
			}
			else {
				dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - price[i]] + price[i]);
			}
		}
		bool flag = false;
		for(int i = X; i >= 0; --i) if(dp[N][i] - 1 >= 0) {
			if(prime[dp[N][i] - 1]) {
				printf("%d\n", dp[N][i]);
				flag = true;
				break;
			}
		}
		if(!flag) printf("NA\n");
	}
	return 0;
}

C++: #include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)

int dt[40];
bool prime[100000];
bool dp[1000000];

int main(void){
	int n, x,lm;
	rep(i,100000){
		prime[i]=true;
	}
	for(int i=2;i<1000000;i++){
		for(int j=i*2;j<1000000;j+=i){
			prime[j]=false;
		}
	}

	while(cin>>n>>lm,n||lm){
		bool find = false;
		rep(i,100000){
			dp[i]=false;
		}
		dp[0] = 1;
		loop(i,0,n){
			cin>>dt[i];
			rep(j,lm){
				dp[j + dt[i]] |= dp[j];
			}
			
		}
		//rep(i,sizeof(okapon))if(okapon[i])cout<<i<<endl;
		for(int i = lm ; i >= 0 ; i --){
			if(i==1){cout<<"NA"<<endl;break;}
			if(dp[i] && prime[i]){cout<<i<<endl;break;}
		}
	}
}

C++: #include<iostream>
#include<cstring>
using namespace std;
??
bool dp[1000010];
int n,x;
int cook[33];
int solve();
bool prime(int now);
??
int main(){
????????while(1){
????????????????cin >> n >> x;
????????????????if(n == 0 && x == 0) break;
????????????????memset(dp,false,x+2);
????????????????dp[0] = true;
????????????????for(int i=0;i<n;i++){
????????????????????????cin >> cook[i];
????????????????????????for(int k=cook[i];k<=x;k++){
????????????????????????????????if(dp[k-cook[i]]){
????????????????????????????????????????dp[k] = true;
????????????????????????????????}
????????????????????????}
????????????????}
????????????????int ans = solve();
????????????????if(ans) cout << ans << endl;
????????????????else cout << "NA" << endl;
????????}
}
??
int solve (){
????????int now = x;
????????while(1){
????????????????if(dp[now] && !(prime(now))) return now;
????????????????now--;
????????}
}
??
bool prime(int now) {
????????for(int i=2;i*i<=now;i++){
????????????????if(now%i == 0) return true;
????????}
????????return false;
}

C++: #include <stdio.h>
#include <algorithm>
using namespace std;
int n, x, a[30]; bool dp[1000001], prime[1000001];
int main() {
	for(int i = 2; i <= 1000000; i++) prime[i] = true;
	for(int i = 2; i <= 1000; i++) {
		if(!prime[i]) continue;
		for(int j = i * i; j <= 1000000; j += i) prime[j] = false;
	}
	while(scanf("%d%d", &n, &x), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n);
		for(int i = 0; i < x; i++) dp[i + 1] = false; dp[0] = true;
		for(int i = 1; i <= x; i++) {
			for(int j = 0; j < n && i >= a[j]; j++) {
				if(dp[i - a[j]]) {
					dp[i] = true; break;
				}
			}
		}
		bool flag = false;
		for(int i = x; i >= 1; i--) {
			if(dp[i] && prime[i]) {
				printf("%d\n", i); flag = true; break;
			}
		}
		if(!flag) printf("NA\n");
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int long long

bool is_prime(int n) {
    if (n==1) {
        return false;
    }
    
    for (int i=2; i*i<=n; i++) {
        if (n%i==0) {
            return false;
        }
    }
    
    return true;
}

signed main() {
    while (true) {
        int n, x;
        cin >> n >> x;
    
        if (n==0 && x==0) {
            break;
        }
        
        vector<int> v;
        
        for (int i=0; i<n; i++) {
            int vi;
            cin >> vi;
            
            while (vi<=x) {
                v.push_back(vi);
                vi *= 2;
            }
        }
        
        int dp[x+1];
        
        for (int i=0; i<=x; i++) {
            dp[i] = 0;
        }
        
        dp[0] = 1;
        
        for (int i=0; i<v.size(); i++) {
            for (int j=0; j<=x; j++) {
                if (dp[j]==1 && j+v[i]<=x) {
                    dp[j+v[i]] = 1;
                }
            }
        }
        
        bool flag = true;
        
        for (int i=x; i>=1; i--) {
            if ((i==1 && dp[i]==1) || (dp[i]==1 && is_prime(i))) {
                cout << i << endl;
                flag = false;
                break;
            }
        }
        
        if (flag) {
            cout << "NA" << endl;
        }
    }
}