fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define all(x) (x).begin(), (x).end()
  6. #define MASK(i) (1LL << (i))
  7. #define BIT(i,n) (((n) >> (i)) & 1LL)
  8.  
  9. typedef long long ll;
  10. typedef pair<int, int> pii;
  11.  
  12. template <class X, class Y> bool mini(X& x, const Y& y) {
  13.     if(x > y){ x = y; return 1; }
  14.     return 0;
  15. }
  16.  
  17. template <class X, class Y> bool maxi(X& x, const Y& y) {
  18.     if(x < y){ x = y; return 1; }
  19.     return 0;
  20. }
  21.  
  22. const int N = 1e6 + 5;
  23. const int S = 200;
  24. const int LOG10 = 15;
  25.  
  26. bitset<S> prime;
  27. ll pow10[LOG10], sum[N], lg10[N], num, l, r, ans = 0;
  28.  
  29. void prepare()
  30. {
  31.     prime.set();
  32.     for(int i = 2; i * i < S; ++i){
  33.         if(!prime[i]) continue;
  34.         for(int j = i * i; j < S; j += i)
  35.             prime[j] = 0;
  36.     }
  37.  
  38.     pow10[0] = 1;
  39.     for(int i = 1; i < LOG10; ++i)
  40.         pow10[i] = pow10[i - 1] * 10;
  41.  
  42.     lg10[0] = sum[0] = 0;
  43.     for(int i = 1; i < N; ++i)
  44.         sum[i] = sum[i / 10] + i % 10, lg10[i] = lg10[i / 10] + 1;
  45. }
  46.  
  47. int rev(int x)
  48. {
  49.     int res = 0;
  50.     while(x) res = res * 10 + x % 10, x /= 10;
  51.     return res;
  52. }
  53.  
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  57.     #define file "PALINPRIME"
  58.     if(fopen(file".inp", "r")){
  59.         freopen(file".inp", "r", stdin);
  60.         freopen(file".out", "w", stdout);
  61.     }
  62.  
  63.     prepare();
  64.     cin >> l >> r;
  65.  
  66.     for(int i = 1; i < N; ++i){
  67.         int revi = rev(i);
  68.         num = 1LL * i * pow10[lg10[i]] + revi;
  69.         if(l <= num && num <= r){
  70.             ans += prime[sum[i] << 1];
  71. //            if(prime[sum[i] << 1]) cerr << num << "\n";
  72.         }
  73.         if(num > r) break;
  74.  
  75.         for(int j = 0; j <= 9; ++j){
  76.             num = 1LL * i * pow10[lg10[i] + 1] + 1LL * j * pow10[lg10[i]] + revi;
  77.             if(l <= num && num <= r){
  78.                 ans += prime[(sum[i] << 1) + j];
  79. //                if(prime[(sum[i] << 1) + j]) cerr << num << "\n";
  80.             }
  81.         }
  82.     }
  83.  
  84.     cout << ans;
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 19200KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BupBm2
language:
C++14 (gcc 8.3)
created:
4 days 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!