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>

using namespace std;

int main() {

    bool P[1000001];
    fill(P, P + 1000001, true);
    P[0] = P[1] = false;

    for (int i = 0; i <= 1000; i++) {
        if (P[i]) {
            for (int j = i * 2; j <= 1000000; j += i) P[j] = false;
        }
    }

    int n, x;
    while (cin >> n >> x) {
        if ((n | x) == 0) break;

        bool dp[x + 1];
        fill(dp, dp + x + 1, false);
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            int v;
            cin >> v;
            for (int j = 0; j <= x - v; j++) {
                if (dp[j] && !dp[j + v])
                    dp[j + v] = true;
            }
        }

        int ans = -1;
        for (int i = x; i >= 0; i--) {
            if (dp[i] && P[i]) {
                ans = i;
                break;
            }
        }

        if (ans != -1) {
            cout << ans << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#define pb push_back
#define f first
#define s second


bool p[1000001];


main(){
  rep(i,1000001)p[i]=true;

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

  int n,x;
  while(cin>>n>>x,n|x){
    int mo[n];
    rep(i,n)cin>>mo[i];
    bool can[x+1];
    memset(can,0,sizeof(can));

    can[0]=1;
    rep(i,x+1){
      if(can[i]){
        rep(j,n){
          if(i+mo[j]<=x)can[i+mo[j]]=1;
        }
      }
    }

    while(true){
      if(can[x] && p[x]){
        cout<<x<<endl;
        break;
      }
      x--;
      if(x<2){
        cout<<"NA"<<endl;
        break;
      }
    }
  }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

int dp[1000001];
int kind[31];


const int MAX_SIZE = 10000;
const int MAX_PRIME = 1000000;


int prime[MAX_PRIME+1];
bool isPrime[MAX_PRIME+1];
int p;

void erats(){
	// primeXgðú»
	fill(isPrime,isPrime+MAX_PRIME,true);
	p = 0;
	isPrime[0] = isPrime[1] = false;

	for(int i = 2; i <= MAX_PRIME; i++){
		if(isPrime[i]){
			prime[p++] = i;
		}
		else
			continue;

		// Óé¢É©¯é
		for(int j = 2*i; j <= MAX_PRIME; j+=i){
			isPrime[j] = false;
		}
		cout << flush;
	}
}


int main(){

	int n;
	int x;
	erats();
	while(cin>>n>>x&&!(n==0&&x==0)){
		for(int i = 0; i < n; i++){
			cin>>kind[i];
		}
		// eàzÌ¥¢ûª½íÞ é©ðßé
		dp[0]=1;
		int maxCost=-1;
		for(int i = 1; i <= x; i++){
			dp[i]=0;
			for(int j = 0; j < n; j++){
				if(i-kind[j]>=0){
					dp[i]+=dp[i-kind[j]];
				}
				else
					break;
			}
			if(dp[i]>=1&&isPrime[i]){
				maxCost=max(i,maxCost);
			}
		}
		if(maxCost==-1)
			cout<<"NA"<<endl;
		else
			cout<<maxCost<<endl;
	}

	return 0;
}

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

int main(){
  //ツ素ツ青板青カツ青ャ
  const int NUM = 1000000;
  bool prime[NUM];
  prime[0] = false;
  prime[1] = false;
  for(int i=2;i<NUM;i++)
    prime[i] = true;
  for(int i=2;i*i<NUM;i++)
    for(int k=2;i*k<NUM;k++)
      prime[i*k]=false;

  while(true){
    int n,x;
    cin>>n>>x;
    if(!n&&!x)break;
    int menu[n];
    for(int i=0;i<n;i++)cin>>menu[i];
    bool money[x+1];
    money[0] = true;
    for(int i=1;i<x+1;i++){
      money[i] = false;
      for(int j=0;j<n;j++){
	if(i>=menu[j]&&money[i-menu[j]]){
	  money[i] = true;
	  break;
	}
      }
    }
    int p = -1;
    for(int i=x;i>0;i--){
      if(prime[i]&&money[i]){
	p=i;
	break;
      }
    }
    if(p==-1)cout<<"NA"<<endl;
    else cout<<p<<endl;
  }
  return 0;
}

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

static const int MAX = 1000001;

int  price[30];
bool dp[MAX];

bool prime( int n );

int main()
{

	int n, x;
	bool flg;

	while( 1 ) {

		flg = false;

		if( cin >> n >> x, n == 0 && x == 0 ) break;

		for( int i = 0; i < MAX; i++ ) dp[i] = false;

		for( int i = 0; i < n; i++ ) cin >> price[i];

		dp[0] = true;

		/*
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < x - price[i]; j++ ) {
			
				if( dp[j] ) dp[j + price[i]] = true;

			}
		}
		*/

		for( int i = 0; i < x; i++ ) {
			if( dp[i] ) {
				for( int j = 0; j < n; j++ ) {
					
					if( i + price[j] <= x ) {
						dp[i + price[j]] = true;
					}
					else continue;

				}
			}
		}

		for( int i = x; i > 0; i-- ) {

			if( dp[i] && prime( i ) ) {
				cout << i << endl;
				flg = true;
				break;
			}

		}

		if( !flg ) cout << "NA" << endl;

	}

	return 0;

}

bool prime( int x )
{

	for( int i = 2; i * i <= x; i++ ) {
		if( x % i == 0 ) return false;
	}

	return true;

}

C++: #include<cstdio>
bool dp[1000001];
bool isprime(int& x){
  for(int i = 2 ; i * i <= x ; i++ ) if( x % i == 0) return true;
  return x == 1;
}
int solve(int& i){
  if( i % 2 == 0 ) i--;
  while(true){
    if(dp[i] && !isprime(i)) return i;
    i -= 2;
  }
}
int main(){
  int n,x,data,ans;
  dp[0] = true;
  while(scanf("%d %d",&n,&x) , n){
    for(int i = 1 ; i <= x ; i++ ) dp[i] = false;
    for(int i = 0 ; i < n ; i++ ){
      scanf("%d",&data);
      for(int i = data ; i <= x ; i++ ) if(dp[i-data]) dp[i] = true;
    }
    if(1 < (ans = solve(x))) printf("%d\n",ans);
    else printf("NA\n");
  }
}