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<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[301];
char memo[1000002];
char sosu[1000002];

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++: #include<iostream>
#include<cstring>
int p[1000100]={};
int u[1000100]={};
#define MAX 1000000
#define rep(i,n) for(int i=0;i<n;i++)
#include<vector>
using namespace std;
int main()
{
    memset(u,0,sizeof(u));
    p[0]=1;
    p[1]=1;
    p[2]=0;
    for(int i=2;i<MAX+1;i++)
        if(p[i] ==0){for(int j=2;(j*i)<MAX+1;j++) {p[ i*j ]=1;}}

    vector<int> primes;
    rep(i,MAX+1){if(!p[i]){primes.push_back(i); /*cout<<i<<" ";*/}}

    int n,x;
    while(cin>>n>>x)
    {
        //cout << n <<" " <<x << endl;
        if(n==0&&x==0){break;}
        memset(u,0,sizeof(u));
        int t;
        u[0]=1;
        int pn = 0;
        int na = 1;
        for(pn=0;primes[pn]<=x ;pn++);
        rep(i,n)
        {
            cin>>t;
            rep(j,x+1)
            {
                if(u[j] == 1 &&(na ))for(int k=1;j+k*t<x+1;k++)
                {
                    u[j+k*t]=1;
                    if(primes[pn]==j+k*t) {na=0;break;}
                }
            }
        }
        //cout << "listed"<<endl;
        for( pn;pn!=0;pn--)
        {
            if(u[primes[pn]] && (!p[primes[pn]])){cout << primes[pn]<<endl; na=0;break;}
        }
        if(na)cout<<"NA"<<endl;
    }

    return 0;
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <limits>
#include <cstring>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

#define LIMIT 1000010
using namespace std;

bool isnotprime[LIMIT] = {0};
bool dp[31][LIMIT] = {0};
int n, x;
int dishes[31];

void erathos()
{
	CLR(isnotprime);
	
	FOR(i, 2, LIMIT)
	{
		if( !isnotprime[i] )
		{
			for(int j = 2; i*j < LIMIT; j++)
			{
				isnotprime[i*j] = true;
			}
		}
	}
	
	return;
}

int solve()
{
	int res = 0;
	
	CLR(dp);
	
	FOR(j, 0, n)
	{
		for(int i = dishes[j]; i <= x; i += dishes[j])
		{
			dp[j][i] = true;
		}
		
		if( j > 0 )
			for(int i = 1; i <= x; i++)
			{
				if(  ( dp[j-1][i] ) || ((i - dishes[j] >= 0) && dp[j-1][i - dishes[j]]) )
				{
					dp[j][i] = true;
				}
			}
	}
	
	RFOR(i, 0, x+1)
	{
		if( !isnotprime[i] && dp[n-1][i] )
		{
			res = i;
			break;
		}
	}
	
	return res;
}

int main()
{
	erathos();
	
	while(cin >> n >> x, (n||x))
	{
		FOR(i, 0, n)
		{
			cin >> dishes[i];
		}
		
		int r = solve();
		
		if(r != 0)
			cout << r << endl;
		else
			cout << "NA" << endl;
	}
		
	return 0;
}

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[]) {
  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;
      }
    }
  }

  // for(i = 0; i <= 1000; i++) {
  //   cout << i << ' ' << dp[i] << endl; 
  // }
  
  for(ans = money; ans > 0; ans--) {
    if(dp[ans] == 1 && 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;
}

C++: #include <iostream>
#include <cstdio>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
#define xMAX 1000001
#define nMAX 31
#define MAX 500001
int v[nMAX];
int dp[nMAX][xMAX];
bool prime[MAX];
int Do,Not;

void sieve(){
  for(int i=0;i<MAX;i++)
    prime[i] = true;

  for(int i = 3; i < xMAX; i += 2)
    for(int j = 3; j * j < i; j += 2)
      if(i % j == 0)
	prime[i/2-1]=false;
}

bool isPrime(int n){
  if(n==0||n==1)
    return false;
  if(n==2)
    return true;
  if(n%2==0)
    return false;
  return prime[n/2-1];
}

void makedp(){
  rep(i,nMAX)
    dp[i][0]=0;
  rep(i,xMAX)
    dp[0][i]=0;
}

void printdp(int n, int x){
  putchar('\n');
  rep(i,n+1){
    printf("%d :",i+1);
    rep(j,x+1){
      printf("%2d ",dp[i][j]);
    }
    putchar('\n'); 
  }
}

void solve(int n, int x){
  int max=0;
  int i,j;

  for(i=1;i<n+1;i++)
    for(j=1;j<x+1;j++){
      Do = dp[i][j-v[i]]+v[i];
      if(Do>x)
	break;
      Not = dp[i-1][j];
      if(j<v[i-1])
	dp[i][j] = Not;
      else{
	if (Do > Not){
	  dp[i][j] = Do;
	  if(max<Do && Do<=x && isPrime(Do))
	    max=Do;
	}
	else
	  dp[i][j] = Not;
      }
    }

  //printdp(n,x);

  if(max)
    cout << max << endl;
  else
    cout << "NA" << endl;
}

int main(){
  sieve();
  makedp();
  v[0]=0;
  for(;;){
    int n,x;
    cin >> n >> x;
    if(!(n+x)) break;
    for(int i=1;i<n+1;i++)
      cin >> v[i];
    solve(n,x);
  }
  return 0;
}