fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define For(i,a,b) for (int i = a ; i <= b ; ++i)
  3. #define Ford(i,a,b) for (int i = a ; i >= b ; --i)
  4. #define ll long long
  5. using namespace std;
  6. ll L,R;
  7. string s;
  8. ll dp[20][200][2];
  9. bool prime[200];
  10.  
  11. bool isPrime(int x){
  12.     if(x < 2) return false;
  13.     for(int i = 2 ; i * i <= x ; i++)
  14.         if(x % i == 0) return false;
  15.     return true;
  16. }
  17.  
  18. int sumDigit(ll x){
  19.     int s = 0;
  20.     while(x){
  21.         s += x % 10;
  22.         x /= 10;
  23.     }
  24.     return s;
  25. }
  26.  
  27. ll sub1(){
  28.     ll ans = 0;
  29.     For(i,L,R){
  30.         if(isPrime(sumDigit(i))) ans++;
  31.     }
  32.     return ans;
  33. }
  34.  
  35. ll digit(int pos,int sum,bool tight){
  36.  
  37.     if(pos == s.size())
  38.         return prime[sum];
  39.  
  40.     if(dp[pos][sum][tight] != -1)
  41.         return dp[pos][sum][tight];
  42.  
  43.     int lim = tight ? s[pos] - '0' : 9;
  44.  
  45.     ll res = 0;
  46.  
  47.     For(d,0,lim)
  48.         res += digit(pos+1,sum+d,tight && (d==lim));
  49.  
  50.     return dp[pos][sum][tight] = res;
  51. }
  52.  
  53. ll solve(ll x){
  54.     s = to_string(x);
  55.     memset(dp,-1,sizeof(dp));
  56.     return digit(0,0,1);
  57. }
  58.  
  59. ll sub2(){
  60.     return solve(R) - solve(L-1);
  61. }
  62.  
  63. int main()
  64. {
  65.     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  66.     freopen("SPECNUM.INP","r",stdin);
  67.     freopen("SPECNUM.OUT","w",stdout);
  68.     cin >> L >> R;
  69.     For(i,0,150) prime[i] = isPrime(i);
  70.     if(R <= 1e5) cout << sub1();
  71.     else cout << sub2();
  72.     return 0;
  73. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZX4HCT
language:
C++14 (clang 8.0)
created:
121 days 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!