fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std; 
  5.  
  6. #define all(v) v.begin(), v.end() 
  7. typedef unsigned long long int ulli; 
  8. typedef long long int ll;
  9.  
  10. vector<ulli> sieve(ulli n) 
  11. { 
  12.  
  13. 	vector<bool> prime(n + 1, true); 
  14.  
  15. 	prime[0] = false; 
  16. 	prime[1] = false; 
  17. 	long long int m = sqrt(n); 
  18.  
  19. 	for (ulli p = 2; p <= m; p++) { 
  20.  
  21. 		// If prime[p] is not changed, then it 
  22. 		// is a prime 
  23. 		if (prime[p]) { 
  24.  
  25. 			// Update all multiples of p 
  26. 			for (ulli i = p * 2; i <= n; i += p) 
  27. 				prime[i] = false; 
  28. 		} 
  29. 	} 
  30.  
  31. 	// push all the primes into the vector ans 
  32. 	vector<ulli> ans; 
  33. 	for (long long int i = 0; i < n; i++) 
  34. 		if (prime[i]) 
  35. 			ans.push_back(i); 
  36. 	return ans; 
  37. } 
  38.  
  39. vector<ulli> sieveRange(ulli start, ulli end) 
  40. { 
  41. 	// find primes from [0..end] range 
  42. 	vector<ulli> ans = sieve(end); 
  43.  
  44. 	// Find index of first prime greater than or 
  45. 	// equal to start 
  46. 	// O(sqrt(n)loglog(n)) 
  47. 	long long int lower_bound_index = lower_bound(all(ans), start) - 
  48. 											ans.begin(); 
  49.  
  50. 	// Remove all elements smaller than start. 
  51. 	// O(logn) 
  52. 	ans.erase(ans.begin(), ans.begin() + lower_bound_index); 
  53.  
  54. 	return ans; 
  55. } 
  56.  
  57. // Driver Program to test above function 
  58. int main() 
  59.  
  60. {
  61.     long long int t,f,l,r;
  62.  
  63.     vector<long long int> a(1000000, 0);
  64.  
  65.     l=1;
  66.     r=600;
  67.     f=0;
  68.  
  69.         map<int,int> a2;
  70.         r++;
  71. 	ulli start = l; 
  72. 	ulli end = r; 
  73. 	vector<ulli> ans = sieveRange(start, end); 
  74. 	for (auto i : ans) 
  75.  
  76. { a[f]=i;
  77. a2[i]++;
  78. 		//cout<<a[f]<<"\n";
  79. f++;
  80. }
  81.  
  82. //cout<<a2[599];
  83.  
  84. ll l1,r1;
  85. cin>>l1>>r1;
  86. ll i;
  87. i=l1;ll c=0;
  88. while(i<=r1)
  89. {
  90.  
  91.     ll k=i;
  92.     ll s=0;
  93.     ll s1=0;
  94.     while(k!=0)
  95.     {
  96.  
  97.         ll gf=k%10;
  98.         s=s+gf;
  99.         s1=s1+(gf*gf);
  100.         k=k/10;
  101.  
  102.     }
  103.  
  104.     if(a2[s]==1 && a2[s1]==1)
  105.     {
  106.         //cout<<i<<"\n";
  107.         c++;
  108.     }
  109.  
  110.  
  111.  
  112.     i++;
  113. }
  114. cout<<c;
  115.  
  116. 	return 0; 
  117. } 
  118.  
Success #stdin #stdout 0.25s 10932KB
comments (?)
stdin
copy 
1 10000000
stdout
copy 
897205
https://ideone.com/CkdwRP
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!