fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const int MAXN = 1e6+5;
  6.  
  7. vector< bool > primes(MAXN+5,true);
  8. vector< int > cnt(MAXN+5,0);
  9. void sieve() {
  10. 	primes[0] = false;
  11. 	primes[1] = false;
  12. 	for (int i=2; i*i<=MAXN; i++) {
  13. 		if (primes[i]) {
  14. 			for (int j=i*i; j<=MAXN; j+=i) {
  15. 				primes[j] = false;
  16. 			}
  17. 		}
  18. 	}
  19. }
  20.  
  21. int main() {
  22. 	sieve();
  23. 	for (int i = 2; i<=MAXN; i++) {
  24. 		cnt[i] += cnt[i-1];
  25. 		if (primes[i]) {
  26. 			if (i > 10) {
  27.  
  28. 				// check if any digit is zero
  29. 				string s = to_string(i);
  30. 				bool z = false;
  31. 				for (auto& e:s) {
  32. 					if (e == '0') z = true;
  33. 				}
  34. 				if (z) {
  35. 					continue;
  36. 				}
  37.  
  38. 				int p = i;
  39. 				// check if all truncations are primes
  40. 				bool y = 1;
  41. 				while (p > 10) {
  42. 					s = to_string(p);
  43. 					s.erase(s.begin());
  44. 					p = stoi(s);
  45. 					y &= primes[p];
  46. 				}
  47. 				if (y) {
  48. 					cnt[i]++;
  49. 				}
  50. 			} else {
  51. 				cnt[i]++;
  52. 			}
  53. 		}
  54. 	}
  55.  
  56. 	int t;
  57. 	cin >> t;
  58. 	for (int tt = 0; tt<t; tt++) {
  59. 		int n;
  60. 		cin >> n;
  61. 		cout << cnt[n] << '\n';
  62. 	}
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0.04s 7104KB
comments (?)
stdin
copy 
10
1
10
20
50
100
1000
1500
10000
100000
1000000
stdout
copy 
0
4
6
10
15
54
58
153
345
671
https://ideone.com/zLed7j
language:
C++14 (gcc 8.3)
created:
3 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!