fork download
  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
stdin
10
1
10
20
50
100
1000
1500
10000
100000
1000000
stdout
0
4
6
10
15
54
58
153
345
671