Paste Search Dynamic
Recent pastes
primesTill
  1. #include <iostream>
  2.  
  3. #include <vector>
  4.  
  5. #include <cmath>
  6.  
  7. #define n 1000000
  8.  
  9. using namespace std;
  10.  
  11. vector<int> prefixsum(n,0);
  12.  
  13. void primesTill() {
  14.  
  15.     vector<int> primes(n+1, 1);
  16.  
  17.     primes[1] = primes[0] = 0;
  18.  
  19.     int val = sqrt(n);
  20.  
  21.     for (int i{2}; i<=val; i++)
  22.  
  23.         if (primes[i] == 1)
  24.  
  25.             for (int j=i; i*j<=n; j++) primes[i*j] = 0;
  26.    
  27.     for(int i=2;i<=n;i++)
  28.     {
  29.         prefixsum[i]=prefixsum[i-1]+primes[i];
  30.     }
  31.  
  32. }
  33.  
  34.  
  35.  
  36. int main() {
  37.        
  38.         primesTill();
  39.  
  40.     int t;
  41.  
  42.     scanf("%d", &t);
  43.  
  44.     while (t--) {
  45.  
  46.         int num;
  47.  
  48.         scanf("%d", &num);
  49.  
  50.         printf("%dn", prefixsum[num]-prefixsum[num/2]);
  51.  
  52.     }
  53.  
  54.     return 0;
  55.  
  56. }
Parsed in 0.003 seconds