Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define N 10050
- using namespace std;
- int n, m, nprimo[N], primo[N], v[N];
- vector<int> primes;
- void crivo()
- {
- nprimo[1] = 1;
- for(int i = 2; i < N; i++)
- {
- if(nprimo[i]) continue;
- for(int j = 2; i *j < N; j++) nprimo[i*j] = 1;
- primes.push_back(i);
- }
- }
- int dp[105][N];
- bool solve(int i, int k)
- {
- if(i > n) return (!nprimo[m - k]);
- if(dp[i][k] != -1) return dp[i][k];
- bool ans = false;
- for(int j = 0; j < primes.size(); j++)
- {
- if(primes[j] * v[i] > k) break;
- ans = (ans or solve(i + 1, k - primes[j]*v[i]));
- }
- return dp[i][k] = ans;
- }
- int main()
- {
- ios::sync_with_stdio(false); cin.tie(0);
- cin>>m>>n;
- for(int i = 1; i <= n; i++) cin>>v[i];
- memset(dp, -1, sizeof dp);
- crivo();
- if(solve(1, m)) cout<<"its primetime\n";
- else cout<<"not primetime\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement