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>
#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;
		}
	}
}


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Ì¥¢ûª½íÞ é©ðßé
		//fill(dp,dp+1000001,0);
		dp[0]=1;
		int maxCost=-1;

		//for(int j = 0; j < n; j++){
		//	for(int i = kind[j]; i <= x; i++){
		//		dp[i]+=dp[i-kind[j]];
		//	}
		//}

		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]];
				}
			}
			if(dp[i]>=1&&(isPrime[i])&&i!=1){
				maxCost=max(i,maxCost);
			}
		}
		//for(int i = 0; i <= x; i++){
		//	if(dp[i]&&isPrime[i])
		//		maxCost=i;
		//}


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

	return 0;
}

C++: #define  _USE_MATH_DEFINES

#define  rep(i, n) for(int i = 0; i < n; i++)
#define  repx(i, a, n) for(int i = a; i < n; i++)
#define  loop while(1)
#define  lli long long int
#define  aryout(ary) rep(i, ary.size()) cout << ary[i] << (i < ary.size() - 1 ? " " : "\n");
#define  arysort(v) sort(v.begin(), v.end())
#define  aryreverse(v) reverse(v.begin(),v.end())ﾎﾉ
#define  arysum(v) accumulate(v.begin(), v.end(), 0)
 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <utility>
#include <set>

using namespace std;

vector<int> subset_sum_total(vector<int> v, int x) {
  
  int n = v.size();
  int sum = x;

  vector<int> tab1(sum + 1, 0);
  tab1[0] = 1;

  rep(i, n) {
    rep(j, sum - v[i] + 1)
      tab1[j + v[i]] += tab1[j];
  }
  return tab1;
}

int main() {

  int n, x;

  loop {
    cin >> n >> x;
    if (n + x == 0) break;

    vector<int> v(n);
    rep(i, n) cin >> v[i];

    vector<int> cost = subset_sum_total(v, x);

    for(int i = cost.size() - 1; i > 0; i--) {
      bool flag = false;
      if (cost[i] > 0) {
        flag = true;
        repx(j, 2, sqrt(i)) {
          if (i % j == 0) {
            flag = false;
            break;
          }
        }
      }
      if (flag) {
        cout << i << endl;
        break;
      }
      else if (i == 1) {
        cout << "NA" << endl;
      }
    }
  }

  return 0;
}

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

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

int sosuu( int a )
{
	if( a < 2 )
	{
		return 0 ;
	}
	else if( a == 2 )
	{
		return 1 ;
	}
	if( a % 2 == 0 )
	{
		return 0 ;
	}
	for( int i = 3 ; i * i <= a ; i += 2 )
	{
		if( a % i == 0 )
		{
			return 0 ;
		}
	}
	return 1 ;
}

int main()
{
	int n ,m ;
	int dmon[ 30 ] ;
	int tmp ;
	while( scanf( "%d %d", &n , &m ), n != 0 )
	{
		for( int i = 0 ; i < n ; i++ )
		{
			cin >> dmon[ i ] ;
			for( int j = 0 ; j < i ; j++ )
			{
				if( dmon[ i ] < dmon[ j ] )
				{
					tmp = dmon[ i ] ;
					dmon[ i ] = dmon[ j ] ;
					dmon[ j ] = tmp ;
				}
			}
		}
		int i ;
		int dp[ 1000000 ] = { 0 } ;
		for( i = 0 ; i + dmon[ 0 ] <= m ; )
		{
			for( int j  = 0 ; j < n ; j++ )
			{
				dp[ i + dmon[ j ] ] = 1 ;
			}
			do
			{
				i++ ;
			}while( dp[ i ] != 1 && i <= m ) ;
		}
		for( int i = m ; i >= 0 ; i-- )
		{
			while( dp[ i ] != 1 )
			{
				i-- ;
			}
			if( tmp = sosuu( i ) > 0 )
			{
				cout << i << endl ;
				goto NEXT ;
			}
		}
		cout << "NA" << endl ;
		NEXT : ;
	}
	return 0 ;
}

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;
		}
	}
}


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Ì¥¢ûª½íÞ é©ðßé
		//fill(dp,dp+1000001,0);
		dp[0]=1;
		int maxCost=-1;

		//for(int j = 0; j < n; j++){
		//	for(int i = kind[j]; i <= x; i++){
		//		dp[i]+=dp[i-kind[j]];
		//	}
		//}

		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]];
				}
			}
			//if(dp[i]>=1&&(isPrime[i])){
			//	maxCost=max(i,maxCost);
			//}
		}
		for(int i = 0; i <= x; i++){
			if(dp[i]&&isPrime[i])
				maxCost=i;
		}


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

	return 0;
}

C++: #include<stdio.h>
int prime[1000001];
int dp[1000001];
int dat[30];
int main(){
	prime[0]=-1;
	prime[1]=-1;
	for(int i=2;i<=1000000;i++){
		if(~prime[i]){
			prime[i]=1;
			for(int j=i*2;j<=1000000;j+=i)prime[j]=-1;
		}
	}
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++){
			scanf("%d",dat+i);
		}
		for(int j=0;j<=b;j++)dp[j]=0;
		dp[0]=1;
		for(int i=0;i<a;i++){
			for(int j=0;j<=b;j++){
				if(dat[i]<=j&&dp[j-dat[i]])dp[j]=1;
			}
		}
		bool dame=true;
		for(int j=b;j>=0;j--){
			if(prime[j]==1&&dp[j]==1){
				dame=false;
				printf("%d\n",j);
				break;
			}
		}
		if(dame)printf("NA\n");
	}
}