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

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

#Debug=True
Debug=False
nmax=1000000
unit_cost = []
total_cost=0
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=[]):
    try:
        uc = unit_cost[lvl]
        if lvl==len(unit_cost)-1:
            yield uc * (money//uc)
        else:
            for i in range(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
    except Exception:
        print('NA')
    

    

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, 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:
            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()
    #    print('NA')
    #    continue

        p=[]
        pmax=-1
        gen=cost_gen1(total_cost, 0)
        for i in gen:
            if i > pmax and prime3(i):
                p.append(i)
                pmax=max(p)
                if pmax==total_cost:
                    break
        print(pmax)
            
        #if Debug:
        #    print('t=', time.time()-t0)
    fh.close()
	            
if __name__ == "__main__":
    main()

Python: def Prime():
    p=[0]*2+[1]*999999
    n = len(p)
    def prime(x):
        for i in range(x + x, n, x):
            p[i] = 0
    prime(2);prime(3);prime(5);prime(7)
    prime(11);prime(13)
    for i in range(15, int(n**0.5)+1,2):
        if (i % 2 and i % 3  and i % 5 and
            i % 7 and i % 11 and i % 13):
            for j in range(i * i, n, i):
                p[j] = 0
    return p

p=Prime()
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: isPrime = [False,True]*500000 + [True] # len:1,000,000
isPrime[1:3] = [False,True]
for i in range(3,1000,2):
    if isPrime[i]:
        isPrime[i*i::2*i] = [False]*len(isPrime[i*i::2*i])

n,x = map(int, input().split())
while n!=0:
    prices = [int(input()) for i in range(n)] # len:n
    isPayable = [False]*(x+1) # len:x+1
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')
    n,x = map(int, input().split())

Python: 
def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)
    for i in range(0, price + 1,ps[0]):
        dp[i >> 5] |= 1 << (i & 31)
    dp[0] = 1
    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        if cur_p >= 32:
            for p in range(cur_p, price + 1, 32):
                i1 = (p - cur_p) >> 5
                i2 = p >> 5
                v = dp[i1]
                dp[i2] |= ((v << r)&(2**33-1)) | rest
                rest = (v >> (32 - r)) & ((1 << r) - 1)
        else:
            for p in range(cur_p, price + 1):
                dp[p >> 5] |= (dp[(p - cur_p) >> 5] >> ((p - cur_p) & 31) & 1) << (p & 31)

    p = -1
    for i in range(price+1, 0,-1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31) & 1):
            p = i
            break
    if p == -1:
        print("NA")
    else:
        print(p)
     
def main():
    N = 1000001
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, int((N+1)**0.5)+1):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))

    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, temp)
 
main()

Python: isPrime = [False,False]+[True]*(1000000-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,x = [int(i) for i in input().split()]
    if n==0: break
    prices = [int(input()) for i in range(n)]
    isPayable = [True]+[False]*x
    for pri in prices:
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    li = [i for i in range(x+1) if isPayable[i] and isPrime[i]]
    print(max(li) if li else 'NA')

Python: def Prime():
    p=[0]*2+[1]*999999
    n = len(p)
    def prime(x):
        for i in range(x + x, n, x):
            p[i] = 0
    prime(2);prime(3);prime(5);prime(7)
    prime(11);prime(13)
    for i in range(15, int(n**0.5)+1,2):
        if (i % 2 and i % 3  and i % 5 and
            i % 7 and i % 11 and i % 13):
            for j in range(i * i, n, i):
                p[j] = 0
    return p
 
p=Prime()
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')