fork download
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4.  
  5. const int maxn = 10005;
  6.  
  7. int v[maxn], primes[1000005], _isprime[1000005];
  8. int psz = 0;
  9.  
  10. void precalc()
  11. {
  12. for (int i = 0 ; i < 1000005; ++i)
  13. _isprime[i] = 1;
  14. for (int i = 2; i < 1000005; ++i)
  15. {
  16. if (_isprime[i])
  17. {
  18. primes[psz++] = i;
  19. for (int j = i << 1; j < 1000005; j += i)
  20. _isprime[j] = 0;
  21. }
  22. }
  23. }
  24.  
  25. inline bool isprime(int x)
  26. {
  27. if (x < 2)
  28. return false;
  29.  
  30. if (x < 1000000) return _isprime[x];
  31. for (int i = 0; primes[i] * primes[i] <= x && i < psz; ++i)
  32. {
  33. if (x % primes[i] == 0)
  34. return false;
  35. }
  36. return true;
  37. }
  38.  
  39. void solve()
  40. {
  41. int n;
  42. scanf("%d", &n);
  43. for (int i = 0; i < n; ++i)
  44. scanf("%d", &v[i]);
  45.  
  46. int ans = -1, ansl = -1, ansr = -1;
  47. for (int len = 2; len <= n && ans == -1; ++len)
  48. {
  49. int sum = 0;
  50. for (int i = 0; i < len; ++i)
  51. sum += v[i];
  52. if (isprime(sum))
  53. {
  54. ans = len;
  55. ansl = 0;
  56. break;
  57. }
  58. for (int i = 0; i + len < n; ++i)
  59. {
  60. sum -= v[i];
  61. sum += v[i+len];
  62. if (isprime(sum))
  63. {
  64. ans = len;
  65. ansl = i+1;
  66. break;
  67. }
  68. }
  69. }
  70. if (ans == -1)
  71. printf("No prime subsequences.\n");
  72. else
  73. {
  74. printf("Shortest prime subsequence length is %d: ", ans);
  75. for (int i = 0; i < ans; ++i)
  76. printf("%d ", v[ansl+i]);
  77. printf("\n");
  78. }
  79. }
  80.  
  81. int main()
  82. {
  83. #ifdef _DEBUG
  84. freopen("input.txt", "r", stdin);
  85. freopen("output.txt", "w", stdout);
  86. #endif
  87.  
  88. precalc();
  89.  
  90. int t;
  91. scanf("%d", &t);
  92. while (t--)
  93. solve();
  94.  
  95. return 0;
  96. }
Time limit exceeded #stdin compilation error #stdout -1s 10576KB
stdin
Standard input is empty
compilation info
prog.cpp: In function ‘void solve()’:
prog.cpp:46: warning: unused variable ‘ansr’
prog.cpp:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp: In function ‘int main()’:
prog.cpp:91: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
Standard output is empty