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")
		}
	}
}

Python: from sys import stdin
readline = stdin.readline


import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

prime = sieve(1000000)


def solve(price, x):
    dp = [0] * (x + 1)
    dp[0] = 1

    price.sort()

    for i in reversed(range(1, len(price))):
        for j in range(i):
            if price[i] % price[j] == 0:
                del price[i]
                break

    for pi in price:
        for i in range(0, len(dp), pi):
            dp[i] = 1
    for pi in price[1:]:
        for i in range(pi, len(dp)):
            if not dp[i] and dp[i - pi]:
                dp[i] = 1
    for i in reversed(range(2, len(dp))):
        if dp[i] and prime[i]:
            return i
    return None

def main():
    while True:
        n, x = map(int, readline().split())
        if n == 0:
            break
        price = [int(readline()) for _ in range(n)]
        amount = solve(price, x)
        print(amount if amount else 'NA')
main()

Python: # -*- coding: utf-8 -*-
import sys,math,time

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
primes=[]
pmax=-1
dic = {2:True,3:True}

def prime3(n):
    global dic
    if n in dic:
        return(dic[n])
    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,math.ceil(math.sqrt(n))+1,2):
                if n % i == 0:
                    dic[n]=False
                    return(False)
            dic[n]=True
            return(True)

def cost_gen1(money, lvl=0, lst=[]):
    uc = unit_cost[lvl]
    if lvl==len(unit_cost)-1:
        yield uc * math.floor(money/uc)
    else:
        for i in range(int(money/uc),-1,-1):
            tot_uc = uc*i
            rem = money - tot_uc
            if rem < unit_cost[lvl+1]:
                yield tot_uc
            else:
                for j in cost_gen1(rem, lvl+1):
                    yield  j + tot_uc

def check_mutually_prime(v):
    s = min(v)
    for i in range(2,s+1):
        if sum(map(lambda x:x%i, v))==0:
            return False
    return True
    
def main():
    global unit_cost, total_cost, primes, pmax
    if not Debug:
        fh=sys.stdin
    else:
        #fh=open('vol2_0202b.txt', 'r')
        fh=open('vol2_0202.txt', 'r')
        #pdb.set_trace()

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0 and total_cost==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v, reverse=True)   # 大きい順
        # 互いに素(relative prime)、でないときの処理
        if not check_mutually_prime(unit_cost):
            print('NA')
            continue
        t0=time.time()
        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            #if i > pmax and i in primes:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(max(p))
            
        if Debug:
            print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Python: def is_prime(n):
    i=2
    while i*i<=n:
        if n%i== 0:return 0
        i+=1
    return 1

while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=1
    for i in range(x,1,-1):
        if is_prime(i) and dp[i]:print(i);break
    else:print('NA')

Python: N=1000000

isPrime = [False,False]+[True]*(N-2)
isPrime[4::2] = [False]*len(isPrime[4::2])
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[2*i::i] = [False]*len(isPrime[2*i::i])

while True:
    n,g = [int(i) for i in input().split()]
    prices = [int(input()) for i in range(n)]
    if n==0 and g == 0: break
    isPayable = [True]+[False]*g
    for pri in prices:
        for i in range(0,g-pri):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(g+1)):
        if i == 0:
            print('NA')
        if isPrime[i] and isPayable[i]:
            print(i)
            break

Python: p=[0]*2+[1]*999999	
for i in range(2,int(1000001**0.5)+1):
    if p[i]:
        for j in range(i*i,1000001,i):
            p[j]=0
while 1:
    n,x=map(int,input().split())
    if n==0:break
    dp=[1]+[0]*(x)
    for i in range(n):
        a=int(input())
        for j in range(a,x+1):
            if dp[j-a]:dp[j]=1
    for i in range(x,1,-1):
        if p[i] and dp[i]:print(i);break
    else:print('NA')

Python: # -*- coding: utf-8 -*-
import sys,time
from math import sqrt, ceil
range=xrange
#Debug=True
Debug=False
nmax=1000000
nmax1=nmax+1
def nums(unit_cost, total_cost):
    cand = [True if i==0 else False for i in range(total_cost+1)]
    for i in range(total_cost+1):
        if cand[i]:
            for j in unit_cost:
                if i + j <= total_cost:
                    cand[i+j]=True
    return(cand)

#dic = {2:True}
def prime3(n):
#    if n in dic:
#        return(dic[n])
#    else:
        if n % 2==0:
            return False
        while True:
            for i in range(3,int(ceil(sqrt(n)))+1,2):
                if n % i == 0:
                    #dic[n]=False
                    return(False)
            #dic[n]=True
            return(True)
    
def main():
    if Debug:
        fh=open('vol2_0202.txt', 'r')
    else:
        fh=sys.stdin

    while True:
        m, total_cost = list(map(int, fh.readline().strip().split()))
        if m==0:
            break
        v=[]
        for _ in range(m):
            v.append(int(fh.readline()))
        unit_cost = sorted(v)

        cand = nums(unit_cost, total_cost)
        for i in range(total_cost,-1,-1):
            if cand[i] and prime3(i):
                print(i)
                break
        if i==0:
            print("NA")

    fh.close()
	            
if __name__ == "__main__":
    main()
    time.sleep(1)

Python: def sieve():
    p = [1] * 1000001
    p[0] = p[1] = 0
    
    for i in range(1000):
        if p[i]:
            for j in range(i * i, 1000001, i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    num[0] = 1
    
    for mi in menu:
        for i in range(len(num) - mi):
            if num[i]:
                pass                
    for i in reversed(range(1, len(num))):
        if p[i] and num[i]:
            return i
    return 'NA'

import sys
f = sys.stdin

p = sieve()
while True:
    
    n, x = map(int, f.readline().split())
    if n == 0:
        break
    menu = [int(f.readline()) for _ in range(n)]
    print(solve(p, menu, x))