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
from math import sqrt, ceil
#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,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")

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

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:
        if num[mi]:
            continue
        for i in range(len(num) - mi):
            if num[i] and not num[i + mi]:
                num[i + mi] = 1
                
    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))

Python: isPrime = [False, True] * 500000
isPrime[1:3] = [False, True]
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)]  # n
	isPayable = [True] + [False] * x  # x+1
	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 sieve(n):
    prime=[]
    is_prime=[True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in xrange(2,n+1):
        if is_prime[i]:
            prime.append(i)
            for j in xrange(2*i,n+1,i):
                is_prime[j]=False
    return prime

def solve():
    prime=sieve(x)
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],prime[-1]+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in reversed(prime):
        if dp[i]:
            return i,True
    return 0,False

while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans,judge=solve()
    print(ans if judge else 'NA')

Python: # AOJ 0202: At Boss's Expense
# Python3 2018.6.26 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

not_prime = [0]*(MAX+3)
def sieve():

	for i in range(3, SQRT, 2):
		if not_prime[i] == 0:
			for j in range(i*i, MAX, i): not_prime[j] = 1
sieve()

while True:
	n, x = map(int, input().split())
	if n == 0: break
	mk, v = [0]*(x+1), [0]*n
	for i in range(n): v[i] = int(input())
	mk[0] = 1
	for k in range(x):
		if mk[k]:
			for i in range(n):
				if k+v[i] <= x: mk[k+v[i]] = 1
	ans = -1
	if x <= 2:
		if mk[x]: ans = x
	else:
		if (x & 1) == 0: x -= 1
		while x > 0:
			if mk[x] and not_prime[x] == 0:
				ans = x
				break
			x -= 2
	print(ans if ans >= 0 else "NA")

Python: from datetime import datetime

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

input = raw_input
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)
    
    for i in range(2, n):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i + i, n, i):
                table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = [False] * (price + 1)

    if ps[0] <= price:
        dp[ps[0]] = True
    dp[0]     = True

    for i in range(1, len(ps)):
        cur_p = ps[i]
        for p in range(price + 1):
            if p >= cur_p:
                dp[p] = dp[p] or dp[p - cur_p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = measure(lambda : init())
    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, table)

main()

Python: def sieve(n):
    p=0
    prime=[0]*n
    is_prime=[True]*(n+1)
    is_prime[0]=is_prime[1]=False
    for i in xrange(2,n+1):
        if is_prime[i]:
            p+=1
            prime[p]=i
            for j in xrange(2*i,n+1,i):
                is_prime[j]=False
    return prime,p

def solve():
    prime,p=sieve(x)
    m=[int(raw_input()) for _ in xrange(n)]
    dp=[False]*(x+1)
    dp[0]=True
    for i in xrange(n):
        for j in xrange(m[i],x+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in xrange(p,0,-1):
        if dp[prime[i]]:
            return prime[i]
    return -1

while 1:
    n,x=map(int,raw_input().split())
    if n==x==0:break
    ans=solve()
    if ans==-1:
        print("NA")
    else:
        print(ans)