fork download 
  1. #include <bits/stdc++.h>
  2. #include <iomanip>
  3. #include<iterator>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. #define ordered_set tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update>
  8. using namespace std;
  9. #define ll long long
  10. #define el "\n"
  11. #define basmala freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
  12. #define int ll
  13. /****************************************************************************/
  14. const int N=2e6+4;
  15. vector<int>pref_primes(N);
  16. /****************************************************************************/
  17. bool isPrime(int x) {
  18.     //sqrt factorizing
  19.     if (x < 2) return false;
  20.     if (x == 2) return true;
  21.     if (x % 2 == 0) return false;
  22.     for (int i = 3; i * i <= x; i += 2) {
  23.         if (x % i == 0) return false;
  24.     } return true;
  25. }
  26. void pre() {
  27.     pref_primes[0] = 0;
  28.     for (int i = 1; i < N; i++) {
  29.         pref_primes[i] = pref_primes[i - 1] + isPrime(i);
  30.     }
  31. }
  32. /****************************************************************************/
  33. void neverland() {
  34.     int q; cin>>q;
  35.     while(q--){
  36.         int n; cin>>n;
  37.         int l=n*(n-1),m=n*n,r=n*(n+1);
  38.         //l->m
  39.         cout<<pref_primes[m]-pref_primes[l-1]<<" ";
  40.         //m->r
  41.         cout<<pref_primes[r]-pref_primes[m-1]<<el;
  42.     }
  43. }
  44. signed main() {
  45.     // basmala;
  46.     //death;
  47.     pre();
  48.     int t=1; //cin>>t;
  49.     while(t--) neverland();
  50. }
Success #stdin #stdout 0.93s 18592KB
comments (?)
stdin 
2
10
25
stdout 
1 4
5 4
https://ideone.com/EcshLK
language:
C++ (gcc 8.3)
created:
12 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!