fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/6tzLg
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!