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

    def get_p(i):
        return dp[i >> 5]
    def set_p(i, v):
        dp[i >> 5] |= v
        
    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

    for i in range(1, len(ps)):
        cur_p = ps[i]
        i1 = cur_p & 31
        rest = 0

        for p in range(cur_p, price + 1, 32):
            v = get_p(p - cur_p)
            rest = (v >> (32 - i1)) & ((1 << i1) - 1)
            set_p(p, (v << i1) | rest)
            if (rest << (32 - i1)) | (v & ((1 << (32 - i1)) - 1)) != v:
                print (rest, v, i1)
            
    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: 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))

    def get_p(i):
        return dp[i >> 5]
    def set_p(i, v):
        dp[i >> 5] |= v
        
    if ps[0] <= price:
        set(ps[0], 1)
    set(0, 1)

    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        
        for p in range(cur_p, price + 1, 32):
            i1 = (p - cur_p) >> 5
            i2 = p >> 5
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            v = dp[i1]
            dp[i2] |= (v << r) | rest
            
            rest = (v >> (32 - r)) & ((1 << r) - 1)
            
    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 = 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 math import sqrt
class Prime:
    """ make prime numbers lists """

    def __init__(self, n):
        self.is_prime = [True for _ in range(n+1)]
        self.primeList = []
        self.is_prime[0] = False
        self.is_prime[1] = False
        for i in range(2, int(pow(n, 0.5))+1):
            if self.is_prime[i] == True:
                self.primeList.append(i)
                for j in range(2*i, n+1, i):
                    self.is_prime[j] = False

    def isPrime(self, n):
        return self.is_prime[n]

    def nthPrime(self, n):
        return self.primeList[n-1]

prime = Prime(10**6)
while True:
    N, X = map(int, input().split())
    if (N, X) == (0, 0): break
    price = [int(input()) for _ in range(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in range(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in range(X, -1, -1):
        if dp[i] == 1 and prime.isPrime(i) == 1:
            print(i)
            break
    else:
        print('NA')

Python: def sieve(n):
    p=0
    prime=[True]*(n+1)
    prime[0]=prime[1]=False
    for i in xrange(2,n+1):
        if prime[i]:
            p=i
            prime[i]=i
            for j in xrange(2*i,n+1,i):
                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],prime[p]+1):
            dp[j]=dp[j]|dp[j-m[i]]

    for i in xrange(p,0,-1):
        if prime[i]:
            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)

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):
            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')