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 hideo[2000001] = { 0 };
int main(void)
{
	int  n, x, temp = 1,noyori=0,debu=0 , ruio[31] = { 0 };
	while (scanf("%d %d", &n, &x)) {
		if (n == 0 && x == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &ruio[i]);
			hideo[ruio[i]] = 1;
		}
		while (temp != x) {
			if (hideo[temp] == 1) {
				for (int j = 1; j <= n; j++) {
					if (hideo[temp + ruio[j]] == 0) {
						hideo[temp + ruio[j]] = 1;
					}
				}
			}
			temp++;
		}
		for (int i = x; i >= 1; i--) {
			if (hideo[i] == 1) {
				for (int j = 2; j < i - 1; j++) {
					if (i%j == 0) {
						debu=1;
					}
				}
				if (debu == 0) {
					noyori = i;
					break;
				}
			}
			debu = 0;
		}
		if (noyori > 1 ) {
			printf("%d\n", noyori);
		}
		else {
			printf("NA\n");
		}
		temp = 1;
		noyori = 0;
		debu = 0;
		for (int i = 1; i <= n; i++) {
			ruio[i] = 0;
		}
		for (int i = 1; i <= x; i++) {
			hideo[i] = 0;
		}
	}
	return 0;
}

C++: #include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
int m[30] = {};
bool p[1000000] = {}, b[1000000] = {};

void calc(int n, int x) {
	rep(i,n) {
		int a = m[i];
		rep2(j,a,x+1) {
			if(b[j-a]) b[j] = 1;
		}
	}
}
int main(){
	int n, x;
	p[0] = p[1] = 1;
	rep2(i,2,1001) {
		if(!p[i]) {
			for(int j = 2*i; j < 1000000; j+=i) {
				p[j] = 1;
			}
		}
	}

	while(cin >> n >> x, (n||x)) {
		fill(m,m+30,0);
		rep(i,n) {
			cin >> m[i];
		}
		rep(i,1000000) {
			b[i] = 0;
		}
		b[0] = 1;
		calc(n,x);
		int i = x;
		for(; i > 0; --i) {
			if(!p[i] && b[i]) {
				cout << i << endl;
				break;
			}
		}
		if(i==0) cout << "NA" << endl;
	}
}

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

char N(int val){
	if(val<0 || val>1000000){
		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--){
			printf("%d\n",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<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> PI;
#define MAX 1000009
ll m=0; int n=0; int ans=0;
bool flag;
/*void dfs(int num){
 if(flag) return;
 if(ans==num){flag=true;return;}
 if(num>ans){memo[num]=false;return;}
 else rep(i,n){
 cout<<num<<endl;
 if(num+v[i]<=ans&&memo[num+v[i]])dfs(num+v[i]);
 }
 memo[num]=false;
 return;
 }*/
int main(){
    vector<bool>check(MAX+1);  //index number will be checked
    rep(i, MAX+1)check[i] = true;
    vector<int>Primenumber(MAX+1,0); //Primearray
    int counter =0;                  //Primearray counter;
    for(int i = 2; i<MAX+1;i++){
        if(check[i]){
            for(int j = 2;i*j<MAX;j++)
                check[i*j] = false;//??´????°??????Primearray????????´???????????????????°??????¨???false???
            Primenumber[counter] = i;
            counter++;
        }
    }
    while(cin>>n>>m,n+m){
        vi v;
        vi hoge;
        int temp;
        flag=false;
        int ans=0;
        rep(i,n){cin>>temp; v.push_back(temp);}
        for(int i=(int)m;i>=0;i--){
            if(check[i]){
                hoge.push_back(i);
            }
        }
        sort(hoge.begin(), hoge.end(), greater<int>());
        bool array[MAX]; rep(i,MAX)array[i]=false;
        rep(i,n)array[v[i]]=true;
        for(int i=1;i<=m;i++) {
            if(array[i])rep(j,n)if(i+v[j]<=m)array[i+v[j]]=true;
        }
        rep(i,hoge.size()){
            
            if(array[hoge[i]]){
                ans=hoge[i]; flag=true; break;
            }
        }
        if(flag) cout<<ans<<endl;
        else cout<<"NA"<<endl;
    }
}

C++: #include <stdio.h>
#include <string.h>

int main(void)
{
	static char prime[1000001];
	static char ok[1000001];
	int i, j;
	int n, t;
	int a[30];
	int max;

	for (i = 3; i <= 1000000; i += 2) {
		prime[i] = 1;
	}
	prime[2] = 1;

	for (i = 3; i <= 1000; i += 2) {
		if (prime[i] == 1) {
			for (j = 3; j <= 1000000 / i; j += 2) {
				prime[i * j] = 0;
			}
		}
	}

	while (1) {
		scanf("%d%d", &t, &n);

		if (t + n == 0) {
			break;
		}

		for (i = 0; i < t; i++) {
			scanf("%d", &a[i]);
		}

		memset(ok, 0, sizeof(ok));
		ok[0] = 1;
		max = -100;
		for (i = 0; i < t; i++) {
			for (j = 0; j + a[i] <= n; j++) {
				if (ok[j] != 0) {
					ok[j + a[i]] = ok[j];
					if (j + a[i] > max && prime[j + a[i]]) {
						max = j + a[i];
					}
				}
			}
		}

		if (max != -100) {
			printf("%d\n", max);
		}
		else {
			printf("NA\n");
		}
	}

	return (0);
}

C++: #include<stdio.h>
long p,cnt,cnt2,food,kakaku[31];
int n,d=0,g,flag,youso[1000001]={0};
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 main()
{
	scanf("%d %ld",&n,&p);
	while(n!=0&&p!=0){
		for(cnt=1;cnt<=n;cnt++){
			scanf("%ld",&food);
			youso[food]=1;
			kakaku[cnt]=food;
		}
		for(cnt=1;cnt<=p;cnt++){
			if(youso[cnt]==1){
				for(cnt2=1;cnt2<=n;cnt2++){
					if(cnt+kakaku[cnt2]<=p){
						youso[cnt+kakaku[cnt2]]=1;
					}
				}
			}
		}
		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;
		for(cnt=1;cnt<=p;cnt++){
			youso[cnt]=0;
		}
		scanf("%d %ld",&n,&p);
	}
	return 0;
}