_no0B

Untitled

Nov 28th, 2021
541
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define N ((int)1e6 + 5)
  4. #define MOD ((int)1e9 + 7)
  5. #define MAX ((int)1e9 + 7)
  6. #define MAXL ((ll)1e18 + 7)
  7. #define MAXP ((int)1e3 + 7)
  8. #define thr 1e-8
  9. #define pi acos(-1)  /// pi = acos ( -1 )
  10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  11. #define endl "\n"
  12.  
  13. using namespace std;
  14.  
  15. int isPrime[N/32 + 2];
  16.  
  17. bool IsPrime(int num) /// returns 1 for prime
  18. {
  19.     if(num == 2) return 1;
  20.     if((num & 1) == 0)  return 0;
  21.     int idx  = num >> 5 , bit = num & 31;
  22.     if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
  23.     else return 1;
  24. }
  25.  
  26. vector < int > Sieve(int n)
  27. {
  28.     for(int i = 3; i * i <= n ; i += 2){
  29.         if(IsPrime(i)){
  30.             for(int j = i * i ; j <= n ; j += i<<1){
  31.                 int idx = j >> 5 , bit = j & 31;
  32.                 isPrime[idx] = isPrime[idx] | (1<<bit);
  33.             }
  34.         }
  35.     }
  36.     vector < int > prime;
  37.     prime.push_back(2);
  38.     for(int i = 3 ; i <= n ; i += 2){
  39.         if(IsPrime(i)) prime.push_back(i);
  40.     }
  41.     return prime;
  42. }
  43.  
  44. bool IsZeroDigit(int num)
  45. {
  46.     while(num > 0){
  47.         if(num % 10 == 0) return true;
  48.         num /= 10; /// num = 123056 -> 12305 -> 1230
  49.     }
  50.     return false;
  51. }
  52.  
  53. bool IsSuffixPrime(int num)
  54. {
  55.     for(int mod = 10 ; ; mod = mod*10){
  56.         int suffix = num % mod;
  57.         if(IsPrime(suffix) == 0) return false;
  58.         if(suffix == num) return true;
  59.     }
  60. }
  61.  
  62. int arr[N];
  63.  
  64.  
  65.  
  66. int main()
  67. {
  68.     /// problem: https://www.spoj.com/problems/VECTAR8/en/
  69.     vector < int > prime = Sieve(1e6);
  70.     for(int p:prime){
  71.         if(IsZeroDigit(p) == false && IsSuffixPrime(p) == true){
  72.             arr[p] = 1;
  73.         }
  74.     }
  75.     for(int i = 1 ; i <= 1e6 ; i++) arr[i] += arr[i-1];
  76.     int t;
  77.     cin>>t;
  78.     while(t--){
  79.         int n;
  80.         cin>>n;
  81.         cout<<arr[n]<<endl;
  82.     }
  83.     return 0;
  84. }
  85.  
  86.  
RAW Paste Data