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: from datetime import datetime

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

input = raw_input
range = xrange
    
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 = [0] * ((price >> 5) + 1)

    def get(i):
        return ((dp[i >> 5] >> (i & 31)) & 1)

    def set(i, v):
        dp[i >> 5] |= (v << (i & 31))

    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

    for i in range(1, len(ps)):
        cur_p = ps[i]
        for p in range(cur_p, price + 1):
            set(p, get(p - cur_p))

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and get(i) == 1:
            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: 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: # -*- 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=[]):
    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, 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)   # 大きい順
        print('NA')
        continue


        # 互いに素(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 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 sieve():
    n = 1000001
    p = [1] * n
    p[0] = p[1] = 0
    
    for i in range(int(n ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def solve(p, menu, x):
    menu.sort()
    
    num = [0] * (x + 1)
    for i in range(0,len(num),menu[0]):
        num[i] = 1
    for mi in menu[1:]:
        for i in range(mi, len(num)):
            if num[i - mi]:
                num[i] = i
    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: #!/usr/bin/env python
# -*- coding: utf-8 -*-
import math

#must import library 'math'
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

primeTable = sieve_of_erastosthenes((10**6))

while True:
    n,x = map(int,raw_input().split())
    if n == 0 and x == 0:
        break
    dishes = []
    dp = [False for i in range(x+1)]
    dp[0] = True
    for i in range(n):
        dishes.append(int(raw_input()))

    ans = 'NA'
    for dish in dishes:
        for i in range(0,x+1):
            if (i + dish < x+1) and dp[i] is not False:
                if primeTable[i+dish] is True:
                    ans = i+dish
                dp[i + dish] = True
    print(ans)