#include #include using namespace std; int dp[10010]; int C[26]; bool is_prime[10010]; int main() { int M, N; cin >> M >> N; fill_n(is_prime, M+1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= M; ++i) { if (!is_prime[i]) continue; for (int j = i + i; j <= M; j += i) { is_prime[j] = false; } } for (int i = 0; i < N; ++i) cin >> C[i]; fill_n(dp, M+1, -1); dp[0] = 0; for (int i = 0; i <= M; ++i) { for (int j = 0; j < N; ++j) { if (i - C[j] >= 0) { if (dp[i - C[j]] >= 0) { dp[i] = max(dp[i], dp[i - C[j]] + 1); } } } } int ans = *max_element(dp, dp + M + 1); for (int i = 0; i <= M; ++i) if (is_prime[i]) { ans += max(dp[M - i], 0); } cout << ans << endl; }