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 <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define INF 1e9


int main(){
    int N = 1e6+1;
    vector<bool> isPrime(N, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i < N; i++) {
        if (!isPrime[i]) continue;
        for (int j = i*i; j < N; j += i) isPrime[j] = false;
    }

    while(true){
        int n,x;
        cin >> n >> x ;
        if(n == 0 && x == 0){
            break;
        }

        vector<int> dishes(n,0);

        FOR(i,0,n){
            cin >> dishes[i];
        }
        vector<bool> dp(x+1,false);
        dp[0] = true;

        int ans = 0;
        for(auto dish:dishes){
            FOR(i,0,x+1){
                if((i+dish < x+1) && dp[i]){
                    if(isPrime[i+dish])
                       ans = i + dish;
                    dp[i+dish] = true;
                }
            }
        }

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

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

int n;
int x;
int d[100];
bool p[1000001];
bool memo[1000001];

int solve(int a,int k){

  if(a > x) return 0;
  if(memo[a]) return memo[a];

  memo[a] = true;

  for(int i=k;i<n;i++) solve(a+d[i],k);

}

int main(){

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

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

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

    solve(0,0);

    int ans = -1;
    for(int i=2;i<x;i++){
      if(memo[i] && p[i]) ans = i;
    }

    if(ans < 0) cout << "NA" << endl;
    else cout << ans << endl;

  }
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
#define MAX 1000000
bool sosu[MAX+1]={1,1,0};
int main(){
  for(int i=4;i<=MAX;i+=2)sosu[i]=true;
  for(int i=3;i<=MAX;i+=2){
    if(sosu[i])continue;
    for(int j=i*3;j<MAX;j+=i*2)sosu[j]=true;
  }
  int n,m;
  while(cin>>n>>m,n||m){
    bool dp[MAX+1]={false};
    vector<int>in(n);
    rep(i,n){cin>>in[i];dp[in[i]]=true;}
    rep(i,n)rep(j,m+1){
      if(dp[j]&&j+in[i]<=MAX)dp[j+in[i]]=true;
    }
    int maxi=0;
    int i=0;
    for(i=m;i>=0;i--)if(!sosu[i]&&dp[i])break;
    if(i!=-1)cout<<i<<endl;
    else cout<<"NA"<<endl;
  }
}

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[1000001]={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;
		for(int i=0;i<1000001;i++){
			youso[i]=0;
		}
		scanf("%d %d",&n,&p);
	}
	return 0;
}

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

using namespace std;

int main(void){
	int n,lim;
	bool isprime[1000001];
	memset(isprime,true,sizeof(isprime));
	isprime[1] = false;
	for(int i=2;i<1000001;i++){
		if(isprime[i] == true){
			for(int j=2;j*i<1000001;j++){
				isprime[i*j] = false;
			}
		}
	}
	
	
	while(cin >> n >> lim){
		if((n|lim) == 0) break;
		vector<int> v;
		int tmp;
		bool creatable[lim+1];
		memset(creatable,false,sizeof(creatable));
		creatable[0] = true;
		
		for(int i=0;i<n;i++){
			cin >> tmp;
			v.push_back(tmp);
		}
		for(int i=0;i<lim;i++){
			if(creatable[i]){
				for(int j=0;j<v.size();j++){
					if(i+v[j] <= lim){
						creatable[i+v[j]] = true;
					}
				}
			}
		}
		
		for(int i=lim;i>=0;i--){
			if(isprime[i] && creatable[i]){
				cout << i << endl;
				break;
			}
			if(i==0){
				cout << "NA" << endl;
				break;
			}
		}
	}
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int n, x, ans;
int in[31], in2[31];
bool dp[1000001];
void solve(int a, int sum){
	for (int i = a; i <= n; i++){
		if (sum + in[i] > x&&!in2[i]){
			in[i] /= 1000;
			in2[i] = 1;
		}
		if (sum + in[i] <= x){
			if (dp[sum + in[i]])
				continue;
			if (sum + in[i] % 2){
				dp[sum + in[i]] = 1;
			}
			solve(i, sum + in[i]);
		}
	}
}
int main(){
	while (cin >> n >> x&&n&&x){
		ans = 0;
		fill(dp, dp + 1000001, 0);
		for (int i = 1; i <= n; i++){
			cin >> in[i];
			in[i] *= 1000;
			in2[i] = 0;
		}
		solve(1, 0);
		for (int i = x; i > 0; i--){
			if (dp[i]){
				for (int j = 5; j <= x; j++){
					if (j == i)
						ans = j;
					if (i % j == 0)
						break;
				}
				if (ans)
					break;
			}
		}
		if (ans)
			cout << ans << endl;
		else
			cout << "NA" << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MAX 1000000
vector<bool> prime(MAX+1,true);
void init(){
	prime[0] = prime[1] = false;
	for(int i=2;i*i<=MAX;i++){
		if(prime[i])for(int j=i*i;j<=MAX;j+=i)prime[j] = false;
	}
}

bool dp[MAX+1] = {0};
int main(){
	init();
	int n,x;
	while(cin >> n >> x, n){
		rep(i,MAX+1)dp[i] = false;		
		dp[0] = true;
		rep(i,n){
			int t;
			cin >> t;
			for(int j=t;j<=MAX;j++){
				dp[j] = dp[j] | dp[j-t];
			}
		}
		while(x){
			if(prime[x] & dp[x]){
				cout << x << endl;
				goto successful;
			}
			x--;
		}
		cout << "NA" << endl;
		successful:;
	}
}