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<stdio.h>
int n,x;
int kin;
int i,j;
int dp[30][1000001];
int flg[1000001];
int main(void){
	for(i=1;i<=1000000;i++){
		flg[i]=1;
	}
	for(i=2;i*i<=1000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<=1000000;j++){
				flg[i*j]=0;
			}
		}
	}
	scanf("%d %d",&n,&x);
	while(n!=0 && x!=0){
		for(i=0;i<n;i++){
			for(j=0;j<=x;j++){
				if(j>0){
					dp[i][j]=-1;
				}
				else if(j==0){
					dp[i][j]=0;
				}
			}
		}
		for(i=0;i<n;i++){
			scanf("%d",&kin);
			for(j=0;j<=x;j++){
				if(dp[i][j]!=-1){
					dp[i][j+kin]=1;
				}
			}
			for(j=0;j<=x;j++){
				dp[i+1][j]=dp[i][j];
			}
		}
		int max=0;
		for(i=0;i<=x;i++){
			if(dp[n][i]==1 && flg[i]==1){
				max=i;
			}
		}
/*		for(i=0;i<=x;i++){
			printf("%d=%d ",i,flg[i]);
		}
		printf("\n");*/
		if(max==0){
			printf("NA\n");
		}
		else {
			printf("%d\n",max);
		}
		scanf("%d %d",&n,&x);
	}
	return 0;
}

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

bool p[1000001];

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

int main(){
    int n, x;
    sieve();

    while(1){
        cin>>n>>x;
        if(!n && !x)break;
        bool dp[1000001]= {false};
        int dish[31];
        for(int i=0;i<n;i++){
            cin>>dish[i];
            dp[dish[i]] = true;
        }
    
        for(int i=0;i<n;i++){
            for(int j=0;j<=1000000;j++){
                if(dp[j] && j+dish[i] <= 1000000)
                    dp[j+dish[i]] = true;
            }
        }
    
        int max=0;
        for(int i=0;i<=x;i++){
            if(dp[i] && p[i])max = i;
        }

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

    return 0;
}

C++: #include<iostream>
#include<vector>
#include<bitset>
#define NMAX 1000001
using namespace std;
int main() {
	vector<char> sosu(NMAX, true);
	for (int i = 2; i < NMAX; ++i) {
		if (sosu[i]) {
			for (int j = i * 2; j < NMAX; j += i) {
				sosu[j] = false;
			}
		}
	}
	
	int num, money;
	while (cin >> num >> money&&num != 0) {
		bitset<NMAX> line;
		line[0] = true;
		for (int i = 0; i < num; ++i) {
			int price;
			cin >> price;
			for (int i = 0, nmax = money - price; i <= nmax; ++i) {
				if (line[i]) {
					line[i + price] = true;
				}
			}
		}
		int ans = -1;
		for (int i = money; i > 0; --i) {
			if (line[i] && sosu[i]) {
				ans = i;
				break;
			}
		}
		if (ans == -1) {
			cout << "NA" << endl;
		}
		else {
			cout << ans << endl;
		}
	}
	return 0;
}

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

using namespace std;

int main() {
	bool p[1000001];
	int n, x;

	p[0] = false;
	p[1] = false;
	for(int i = 2; i <= 1000000; i++) {
		p[i] = true;
	}

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

	while( true ) {
		cin >> n >> x;

		if(n == 0 && x == 0) {
			break;
		}

		vector< int > dp(x + 1, 0);
		vector< int > money(n);

		for(int i = 0; i < n; i++) {
			cin >> money[i];
		}

		for(int i = 0; i < n; i++) {
			dp[money[i]]++;
		}

		for(int i = 0; i <= x; i++) {
			for(int j = 0; j < n; j++) {
				if(dp[i] == 0 || (i + money[j]) > x) {
					continue;
				}
				dp[i + money[j]]++;
			}
		}

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

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

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

#define MAXNUM 1000001

bool prime[MAXNUM];

void eratosthenes()
{
	prime[0]=prime[1]=false;

	for(int i=2; i<MAXNUM; i++)
	{
		prime[i]=true;
	}
	
	for(int i=2; i*i<MAXNUM; i++)
	{
		if(prime[i])
		{
			for(int j=i*i; j<MAXNUM; j+=i)
			{
				prime[j]=false;
			}
		}
	}
}


bool dp[1000001];

int main()
{
	eratosthenes();
	int N,B,c[30];
	while(cin >> N >> B)
	{
		int sum=0;
		memset(dp,0,sizeof(dp));
		for(int i=0; i<N; i++)
		{
			cin >> c[i];
			sum+=c[i];
		}
			
		dp[0]=1;
		
		for(int i=0; i<N; i++)
		for(int j=0; j<B; j++)
		{
			if(j+c[i]>B) break;
			if(dp[j]) dp[j+c[i]]=1;
		}
		
		bool g=false;;
		for(int i=B; i>0; i--)
		{
			if(i==sum) continue;
			if(dp[i]&&prime[i])
			{
				g=true;
				cout << i << endl;
				break;
			}
		}
		if(!g) cout << "NA" << endl;
	}
}

C++: #include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define MP 10000001
using namespace std;
bool p[MP]; int n,x,c[35],ans;
bool rec(int a,int s){
	int f=0;
	for(int i=s;i<n&&a>=c[i];i++)if(i>0||c[i]!=c[i-1]){
		if(a==c[i])return 1;
		else{
			f=rec(a-c[i],i);
			if(f) return 1;
		}
	}
	return f;
}
int main(){
	for(int i=2;i*i<MP;i++)if(!p[i])for(int j=i+i;j<MP;j+=i)p[j]=1;
	p[0]=p[1]=1;
	while(cin>>n>>x,n){
		rep(i,n)cin>>c[i]; sort(c,c+n);
		for(ans=x;ans>=c[0];ans--)if(!p[ans]&&rec(ans,0))break;
		if(ans<c[0])cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

C++: #include<stdio.h>
int n,x;
int i,j;
bool k[1000001];
bool l[1000001];
int p[30];

int max(int a,int b){return a>b?a:b;}

int comp(const void *a,const void *b){
	int *p=(int*)a;
	int *q=(int*)b;
	return *q-*p;
}

int main(){
	while(1){
		scanf("%d %d",&n,&x);
		if(n==0&&x==0)return 0;
		for(i=0;i<=x;i++)k[i]=false;
		for(i=0;i<=x;i++)l[i]=true;
		for(i=0;i<n;i++){
			scanf("%d",&p[i]);
			k[p[i]]=true;
		}
		for(i=1;i<=x;i++){
			if(k[i]){
				for(j=0;j<n;j++)if(i+p[j]<=x)k[i+p[j]]=true;
			}
		}
		int ans=0;
		for(i=2;i<=x;i++){
			if(l[i]){
				for(j=1;j*i<=x;j++){
					l[j*i]=false;
				}
				if(k[i])ans=max(ans,i);
			}
		}
		if(ans==0)printf("NA\n");
		else printf("%d\n",ans);
	}
}

C++: #include <iostream>
#include <string.h>
#include <math.h>

using namespace std;

const int N = 1000000;

int prime[N+1];
int table[N+1];
int dish[30];
int n, x;
int max_val;
int cnt;

void setPrime()
{
	memset(&prime[0], 0, sizeof(int) * (N+1));
	prime[2] = 1;
	for(int i=2; i<=N; i++)
	{
		bool is_prime = true;
		int limit = sqrt(i);
		for(int k=2; k<=limit; k++)
		{
			if(i % k == 0)
			{
				is_prime = false;
				break;
			}	
		}
		
		if(is_prime)
		{
			prime[i] = 1;
		}
	}
}

void solve(int price)
{
	cnt++;
	
	if(price > x)
	{
		return;
	}
	
	if(table[price] == 1)
	{
		return;
	}
	else
	{
		table[price] = 1;
	}
	
	if(prime[price] == 1 && max_val < price)
	{
		max_val = price;
	}
	
	for(int k=0; k<n; k++)
	{
		solve(price + dish[k]);
	}
}

int main()
{
	setPrime();
	
	while( 1 )
	{
		cin >> n >> x;
		if(n==0 && x==0)
		{
			break;
		}
		
		clock_t t = clock();
		for(int i=0; i<n; i++)
		{
			cin >> dish[i];
		}
		
		memset(&table[0], 0, sizeof(int)*(N+1));
		max_val = 0;
		cnt = 0;
		solve(0);
		
		if(max_val != 0)
		{
			printf("%d\n", max_val);
		}
		else
		{
			printf("NA\n");
		}
	}
}