fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. #define all(x)  x.begin(),x.end()
  11. #define v(x) vector<x>
  12. #define nl '\n'
  13. #define fxd(x) fixed << setprecision(x)
  14. template<class t> using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  15. template<class t> using ordered_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;
  16.  
  17. vector<bool> nums(1000005,true);
  18. ll sz = nums.size()-1;
  19. void sieve()
  20. {
  21.     nums[0] = false;
  22.     nums[1] = false;
  23.     for (ll i = 2; i < nums.size(); i++)
  24.     {
  25.         if(nums[i])
  26.         {
  27.             for (ll j = i*i; j < sz; j+=i)
  28.             {
  29.                 nums[j] = false;
  30.             }
  31.  
  32.         }
  33.     }
  34.     return;
  35. }
  36.  
  37. bool feared(ll n)
  38. {
  39.     while(n)
  40.     {
  41.         if(n%10 == 0)
  42.         {
  43.             return false;
  44.         }
  45.         n/=10;
  46.     }
  47.     return true;
  48. }
  49.  
  50. bool alltruncates(ll n)
  51. {
  52.     ll p = log10(n);
  53.     while (p--)
  54.     {
  55.         if(!nums[n%(ll)pow(10,p+1)]) return false;
  56.     }
  57.     return true;
  58. }
  59.  
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  63.     sieve();
  64.     int t; cin >> t;
  65.     v(ll) pref(sz,0);
  66.     for (int i = 1; i < sz; i++)
  67.     {
  68.         if(nums[i] && feared(i) && alltruncates(i)) pref[i]++;
  69.         pref[i] = pref[i-1] + pref[i];
  70.     }
  71.     while (t--)
  72.     {
  73.         ll n; cin >> n;
  74.         cout << pref[n] << nl;
  75.     }
  76. }
Success #stdin #stdout 0.02s 11080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S3n4hX
language:
C++ (gcc 8.3)
created:
4 hours 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!