fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define PB push_back
  5. #define EB epmplace_back
  6. #define REP(i,a,b) for(ll i=a;i<=b;i++)
  7. typedef vector<bool> vb;
  8. typedef vector<ll> vll;
  9. typedef vector<int> vi;
  10. const ll MAX = 100001;
  11.  
  12. vb is_prime(MAX, true);
  13. vi primes_till(MAX,0);
  14.  
  15. void sieve()
  16. {
  17. 	is_prime[0]=is_prime[1]=false;
  18. 	for(ll i=2;i<MAX;i++)
  19. 		if(is_prime[i])
  20. 			for(ll j=i*2;j<MAX;j+=i)
  21. 				is_prime[j]=false;
  22. }
  23.  
  24. void primes_in_range()
  25. {
  26. 	REP(i,2,MAX-1)
  27. 	{
  28. 		if(is_prime[i])
  29. 			primes_till[i]=primes_till[i-1]+1;
  30. 		else
  31. 			primes_till[i]=primes_till[i-1];
  32. 	}
  33. }
  34.  
  35. int main() {
  36. 	sieve();
  37. 	primes_in_range();
  38. 	int t;
  39. 	cin>>t;
  40. 	while(t--)
  41. 	{
  42. 		ll n,k;
  43. 		cin>>n>>k;
  44. 		if (n < 4) {
  45.             cout << "0 0\n";
  46.             continue;
  47. 		}
  48. 		n = sqrt(n);
  49. 		k = sqrt(k);
  50. 		if(k>n)
  51. 			cout<<primes_till[n]<<" 0\n"<<endl;
  52. 		else
  53. 			cout<<primes_till[n]<<" "<<primes_till[n]-primes_till[k]<<endl;
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
3
10 2
20 7
10 4
stdout
copy 
2 2
2 1
2 1
https://ideone.com/lm5IMM
language:
C++14 (gcc 8.3)
created:
3 years 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!