Advertisement
Guest User

Bob Primes

a guest
Aug 20th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define N 10050
  3. using namespace std;
  4.  
  5. int n, m, nprimo[N], primo[N], v[N];
  6.  
  7. vector<int> primes;
  8.  
  9. void crivo()
  10. {
  11. nprimo[1] = 1;
  12.  
  13. for(int i = 2; i < N; i++)
  14. {
  15. if(nprimo[i]) continue;
  16.  
  17. for(int j = 2; i *j < N; j++) nprimo[i*j] = 1;
  18.  
  19. primes.push_back(i);
  20. }
  21. }
  22.  
  23. int dp[105][N];
  24.  
  25. bool solve(int i, int k)
  26. {
  27. if(i > n) return (!nprimo[m - k]);
  28.  
  29. if(dp[i][k] != -1) return dp[i][k];
  30.  
  31. bool ans = false;
  32.  
  33. for(int j = 0; j < primes.size(); j++)
  34. {
  35. if(primes[j] * v[i] > k) break;
  36.  
  37. ans = (ans or solve(i + 1, k - primes[j]*v[i]));
  38. }
  39.  
  40. return dp[i][k] = ans;
  41. }
  42.  
  43. int main()
  44. {
  45. ios::sync_with_stdio(false); cin.tie(0);
  46.  
  47. cin>>m>>n;
  48.  
  49. for(int i = 1; i <= n; i++) cin>>v[i];
  50.  
  51. memset(dp, -1, sizeof dp);
  52.  
  53. crivo();
  54.  
  55. if(solve(1, m)) cout<<"its primetime\n";
  56.  
  57. else cout<<"not primetime\n";
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement