At Boss's Expense

At Boss's Expense

一発で書けた。素数とナップザック問題。

bool dp[35][1000005];
bool pt[1000005];

int main() {
    memset(pt, 1, sizeof(pt));
    pt[0] = 0; pt[1] = 0;
    for (int i = 2; i * i < 1000005; i++) {
        if (pt[i]) {
            for (int j = i*2; j < 1000005; j+=i) {
                pt[j] = 0;
            }
        }
    }
    while (1) {
        int n, x; cin >> n >> x;
        if (n == 0 && x == 0) break;
        int v[35]; memset(v, 0, sizeof(v));
        for (int i = 0; i < n; i++) cin >> v[i];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= x; j++) {
                if (j - v[i] >= 0)
                    dp[i + 1][j] |= dp[i + 1][j - v[i]];
                dp[i + 1][j] |= dp[i][j];
            }
        }
        int res = -1;
        for (int i = 2; i <= x; i++) {
            if (dp[n][i] && pt[i]) {
                res = max(res, i);
            }
        }
        if (res != -1)
            cout << res << endl;
        else
            cout << "NA" << endl;
    }

    return 0;
}