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; }