fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. vector<long long> primes;
  8.  
  9. void precalc()
  10. {
  11. 	int n = 1e6 + 5;
  12. 	vector<int> sieve(n, 1);
  13. 	for (long long i = 2; i < n; i++)
  14. 	{
  15. 		if (sieve[i])
  16. 		{
  17. 			primes.push_back(i);
  18. 			for (long long j = i * i; j < n; j += i)
  19. 			{
  20. 				sieve[j] = 0;
  21. 			}
  22. 		}
  23. 	}
  24. }
  25.  
  26. int main()
  27. {
  28. 	int n;
  29. 	cin >> n;
  30. 	vector<int> a(n + 1);
  31. 	for (int i = 1; i <= n; i++)
  32. 	{
  33. 		cin >> a[i];
  34. 	}
  35. 	precalc();
  36. 	vector<long long> div3, div4;
  37. 	for (int i = 0; i < primes.size(); i++)
  38. 	{
  39. 		if (primes[i] <= 100)
  40. 		{
  41. 			div4.push_back(primes[i] * primes[i] * primes[i]);
  42. 		}
  43. 		if (primes[i] <= 1000)
  44. 		{
  45. 			div3.push_back(primes[i] * primes[i]);
  46. 			for (int j = 0; j < i; j++)
  47. 			{
  48. 				if (primes[j] * primes[i] > n) break;
  49. 				div4.push_back(primes[i] * primes[j]);
  50. 			}
  51. 		}
  52. 	}
  53. 	long long x = 0, y = 0, z = 0;
  54. 	for (int i = 0; i < primes.size(); i++)
  55. 	{
  56. 		if (primes[i] <= n)
  57. 			x += a[primes[i]];
  58. 	}
  59. 	for (int i = 0; i < div3.size(); i++)
  60. 	{
  61. 		if (div3[i] <= n)
  62. 			y += a[div3[i]];
  63. 	}
  64. 	for (int i = 0; i < div4.size(); i++)
  65. 	{
  66. 		if (div4[i] <= n)
  67. 			z += a[div4[i]];
  68. 	}
  69. 	cout << x << " " << y << " " << z;
  70. 	return 0;
  71. }
Success #stdin #stdout 0.01s 8096KB
comments (?)
stdin
copy 
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
stdout
copy 
8 2 5
https://ideone.com/Ym97oj
language:
C++14 (gcc 8.3)
created:
4 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!