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 <bits/stdc++.h>
using namespace std;
bool e[1000001],dp[1000010];
int main(){
  e[0]=e[1]=1;
  for(int i=2;i<1000001;i++)
    for(int j=i*2;j<1000001;j+=i)
      e[j]=1;
  int n,m;
  while(cin>>n>>m,n){
    for(int i=0;i<m+3;i++)dp[i]=0;
    int a[n],c=1,p;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
      for(int j=1;j<=m;j++){
        if(dp[j]&&!dp[a[i]+j])dp[a[i]+j]=1;
        if(a[i]*j<=m)dp[a[i]*j]=1;}
    for(p=m;p>=0;p--)if(dp[p]&&!e[p]){c=0;break;}
    if(c)cout<<"NA"<<endl;
  else cout<<p<<endl;
  }
}

C++: #include <cstdio>
#include <cstring>
int cook[30];
bool dp[1000001],prime[1000001];
int main() {
	for(int i=2;i*i<=1000000;i++) {
		if(prime[i]) continue;
		for(int j=i*2;j<=1000000;j+=i) prime[j]=true;
	}
	int n,x;
	while(scanf("%d %d",&n,&x),n) {
		for(int i=0;i<n;i++) {
			scanf("%d",&cook[i]);
		}
		memset(dp,0,sizeof(dp));
		dp[0]=true;
		for(int i=0;i<n;i++) {
			for(int j=0;j<=x;j++) {
				if((j-cook[i])>=0) dp[j]|=dp[j-cook[i]];
			}
		}
		bool NA=true;
		for(int i=x;i>0;i--) {
			if(dp[i]&&!prime[i]) {
				printf("%d\n",i);
				NA=false;
				break;
			}
		}
		if(NA) printf("NA\n");
	}
}

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

using namespace std;

bool prime[1000001],dp[1000001];

void make_prime(){
  for(int i=0;i<1000001;i++) prime[i]=true;
  prime[0]=prime[1]=false;
  for(int i=2;i<=1000000;i++){
    if(prime[i]){
      for(int j=i*2;j<1000001;j+=i){
          prime[j]=false;
        }
    }
  }
}

int n,x;
vector<int> price;

int main(){
  make_prime();

  while(cin>>n && n){
    cin>>x;
    for(int i=0;i<1000001;i++){
      dp[i]=false;
    }
    for(int i=0;i<n;i++){
      int tmp;
      cin>>tmp;
      price.push_back(tmp);
      dp[tmp]=true;
    }

    sort(price.begin(),price.end());

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

    int ans=0;

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

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

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

using namespace std;

int main(){
	bool sosuu[1000011];
	bool dp[1000011];
	
		for(int i=0;i<=1000000;i++){
			sosu[i]=0;
		}
		for(int i=2;i<=500000;i++){
			if(sosuu[i]==0){
				for(int j=i;j<=1000000;j+=i){
					sosuu[j]=1;
				}
				sosuu[i]=0;
			}
		}
		sosuu[0]=1;
		sosuu[1]=1;
	while(1){
		for(int i=0;i<=1000000;i++){
			dp[i]=0;
		}
		
		int item[30];
		
		int n,m;
		scanf("%d%d",&n,&m);
		
		if(n==0 && m==0){
			break;
		}
		for(int i=0;i<n;i++){
			scanf("%d",&item[i]);
		}
		dp[0]=1;
		for(int i=0;i<=m;i++){
			for(int j=0;j<n;j++){
				if(i<item[j]){
					continue;
				}
				if(dp[i-item[j]]==1){
					dp[i]=1;
				}
			}
		}
		int num=0;
		for(int i=m;i>=0;i--){
			if(dp[i]==1&&sosuu[i]==0){
				num=i;
				break;
			}
		}
		if(num==0){
			puts("NA");
		}else{
			printf("%d\n",num);
		}
	}
}

C++: #include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
using namespace std;


int n, x;
int m[40];
int dp[1000010];
int p[1000000];


void sieve(){
	memset(p, 1, sizeof p);
	p[0] = p[1] = 0;
	for(int i = 2;i*i <= 1000000;i++){
		if(p[i]){
			for(int j = 2;i*j <= 1000000;j++)
				p[i*j] = 0;
		}
	}
}


void makeDP(){
	rep(i, 1, n+1){
		rep(j, 0, x+1){
			if(j >= m[i]) dp[j] = max(dp[j], dp[j-m[i]] + m[i]);
		}
	}
}


int main(){
	sieve();

	while(cin >> n >> x, n || x){
		rep(i, 1, n+1) cin >> m[i];

		makeDP();
		
		int ans = -1;
		repr(i, x, -1){
			if(p[dp[i]]){
				ans = dp[i];
				break;
			}
		}

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

	return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; i++)

bool is_prime(int n) {
    if (n % 2 == 0) return false;
    for (int i = 3; i <= std::sqrt(n); i += 2)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n, x;
    while (std::cin >> n >> x && n > 0 && x > 0) {
        bool course[x + 1];
        rep(i, x + 1) course[i] = false;

        int prices[n];
        rep(i, n) {
            std::cin >> prices[i];
            course[prices[i]] = true;
        }

        rep(i, x + 1) rep(j, n) {
            if (i - prices[j] > 0 && course[i - prices[j]]) course[i] = true;
        }
        bool flag = false;
        for (int i = x; i > 1; i--)
            if (course[i] && is_prime(i)) {
                flag = true;
                std::cout << i << std::endl;
                break;
            }

        if (!flag) std::cout << "NA" << std::endl;
    }
    return EXIT_SUCCESS;
}

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

#define MAX_P 1000000

int main(){
	bool prime[MAX_P];
	prime[0] = false;
	prime[1] = false;
	for( int i = 2; i < MAX_P; i++ ) prime[i] = true;
	for( int i = 2; i < MAX_P; i++ ){
		if( prime[i] ){
			for( int j = 2*i; j < MAX_P; j += i ){
				prime[j] = false;
			}
		}
	}
	int n, x;
	while( cin >> n >> x, n || x ){
		vector<bool> dp(x+1);
		for( int i = 0; i <= x; i++ ) dp[i] = false;
		vector<int> p(n);
		for( int i = 0; i < n; i++ ){
			cin >> p[i];
		}
		dp[0] = true;
		int max = 0;
		for( int i = 0; i <= x; i++ ){
			if( dp[i] ){
				if( prime[i] && max < i ) max = i;
				for( int j = 0; j < n; j++ ){
					dp[i+p[j]] = true;
				}
			}
		}
		if( max > 0 ) cout << max << endl;
		else cout << "NA" << endl;
	}
}

C++: #include<iostream>
#include<vector>
#include<stack>
#include<cmath>

using namespace std;

#define NUM 1000000
int money, n;
int prime[NUM];
int dp[NUM+1] = {};

int cal(int cost[]) {
  stack <int> s;
  int i, j;
  int ans;
  for(i = 0; i <= money; i++) {
    dp[i] = 0;
  }
  
  dp[0] = 1;
  // for(i = 0; i < n; i++) {
  //   dp[cost[i]] = 1;
  // }

  for(i = 1; i <= money; i++) {
    for(j = 0; j < n; j++) {
      if(i - cost[j] >= 0 && dp[i - cost[j]] == 1) {
	dp[i] = 1;
	s.push(i);
      }
    }
  }

  // for(i = 0; i <= 1000; i++) {
  //   cout << i << ' ' << dp[i] << endl; 
  // }
  
  while(s.size() > 0) {
    ans = s.top();
    s.pop();
    if(prime[ans] == 1) {
      cout << ans << endl;
      return 0;
    }
  }
  cout << "NA" << endl;
  return 1;
}
  
int main() {
  int i, j;
  int sq_num = (int)sqrt((double)NUM);

  for (i = 0; i < NUM; i++)
    prime[i] = 1;  
  prime[0] =  prime[1] = 0;    
  
  for (i = 1; i < sq_num; i++) {
    if (prime[i] == 1)         
      for (j = 2; i * j <= NUM; j++) {
	prime[j*i] = 0;
      }
  }
  
  while(cin >> n >> money, n != 0 || money != 0) {
    int cost[n + 1] = {};
    for(i = 0; i < n; i++) {
      cin >> cost[i];
    }
    
    cal(cost); 
  }
  
  return 0;
}