Niloy007

Hackerrank

May 13th, 2020
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define max 1000000
  3. #define FastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
  4. using namespace std;
  5.  
  6. int sum(int a) {
  7.     int sum = 0;
  8.     while(a) {
  9.         sum += (a % 10);
  10.         a = a / 10;
  11.     }
  12.     return sum;
  13. }
  14.  
  15.  
  16. void sieve(vector<int> &Prime) {
  17.     vector<int> isPrime(max, 1);
  18.  
  19.  
  20.     // Sieve
  21.     for (int i = 2; i * i <= max; i++) {
  22.         if(isPrime[i]) {
  23.             for (int j = i * i; j <= max; j += i) {
  24.                 isPrime[j] = 0;
  25.             }
  26.         }
  27.     }
  28.  
  29.     // Store primes in Prime vector
  30.     for(int i=2; i<=1000000; i++) {
  31.         if(isPrime[i] != 0 && isPrime[sum(i)] != 0)
  32.             Prime.push_back(i);
  33.     }
  34. }
  35.  
  36.  
  37. int main() {
  38. #ifdef Niloy
  39.     freopen("input.txt", "r", stdin);
  40.     freopen("output.txt", "w", stdout);
  41. #endif
  42.     FastInput;
  43.     vector<int> Prime;
  44.     sieve(Prime);
  45.     int l, r, t;
  46.     cin >> t;
  47.     while(t--) {
  48.         cin >> l >> r;
  49.         int low = lower_bound(Prime.begin(), Prime.end(), l) - Prime.begin();
  50.         int high = lower_bound(Prime.begin(), Prime.end(), r) - Prime.begin();
  51.         if(high == Prime.size() || Prime[high] > high)
  52.             high -= 1;
  53.         cout << (high - low) + 1 << endl;
  54.     }
  55.     return 0;
  56. }
RAW Paste Data