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: input = raw_input

def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def is_prime(p):
    if p == 0 or p == 1:
        return False
    for i in range(2, p - 1):
        if p % i == 0:
            return False
    return True

def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    dp[0][ps[0]] = True
    dp[0][0]     = True

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

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = 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: from bisect import bisect_left as bl
def main():
  tf = [True] * 1000004
  tf[0] = tf[1] = False
  for i in range(2, 1001):
    if tf[i]:
      for j in range(i ** 2 , 1000004, i):
        tf[j] = False
  primes = [i for i in range(1000004) if tf[i]]
  
  while True:
    n, x = map(int, input().split())
    if n == 0:
      break
    can = [False] * (x + 1)
    can[0] = True
    for _ in range(n):
      v = int(input())
      for i in range(x - v + 1):
        if can[i] and not can[i + v]: can[i + v] = True
    can_nums = [i for i in range(x, -1, -1) if can[i]]
    for num in can_nums:
      if primes[bl(primes, num)] == num:
        print(num)
        break
    else:
      print("NA")
   
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] * (max(menu) + x + 1);num[0] = 1 
    
    for i in range(x + 1):
        for mi in menu:
            if num[i - mi]:
                num[i] = 1
                break
    for i in reversed(range(1, x + 1)):
        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: # AOJ 0202: At Boss's Expense
# Python3 2018.6.26 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

not_prime = [0]*MAX
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 math import sqrt
prime = [1 for _ in xrange(10**6+1)]
prime[1] = 0
prime[0] = 0
for i in xrange(2, int(sqrt(10**6+1))+1):
    if prime[i] == 1:
        for j in xrange(i+i, 10**6+1, i):
            prime[j] = 0
while True:
    N, X = map(int, raw_input().split())
    if (N, X) == (0, 0): break
    price = [input() for _ in xrange(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in xrange(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in xrange(X, -1, -1):
        if i > 0 and dp[i] == 1 and prime[i] == 1:
            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: 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: isPrime = [False,False]+[True]*(1000000)
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 = [False]*(x+1)
    for pri in prices:
        isPayable[pri] = True
        for i in range(0,x-pri+1):
            if isPayable[i]:
                isPayable[i+pri] = True
    for i in reversed(range(x+1)):
        if isPayable[i] and isPrime[i]:
            print(i)
            break
        if i == 0:
            print('NA')

Python: MAX_X = 1000000 
isPrime = [True] * (MAX_X + 1)
isPrime[0] = isPrime[1] = False
for i in xrange(2, int(MAX_X ** 0.5) + 1):
    if isPrime[i]:
        for j in xrange(i + i, MAX_X + 1, i):
            isPrime[j] = False

while True:
    n, x = map(int, raw_input().split())
    if n | x == 0:
        break
    dp = [False] * (x + 1)
    dp[0] = True
    for _ in xrange(n):
        c = int(raw_input())
        for i in xrange(x + 1 - c):
            if dp[i]:
                dp[i + c] = True
    print (["NA"] + filter(lambda x: dp[x] and isPrime[x], xrange(x + 1)))[-1]