fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ul unsigned long long
  6.  
  7. ll mod = 1e9+7;
  8. const int N = 1e5+5;
  9. const int n = 1e7;
  10. int MOD = 998244353;
  11. int bit[200000];
  12. bool p[n+5];
  13. int t[n+5];
  14. void sang(){
  15. 	memset(p, true, sizeof(p));
  16. 	p[0]=0;
  17. 	p[1]=0;
  18. 	for (int i = 2; i <= n; i++) {
  19. 			if (p[i]) {
  20.                 for (ll j = i * i; j <= n; j += i){
  21.  
  22.                     p[j] = false;
  23.  
  24.                 }
  25.  
  26.             }
  27.  
  28. 	}
  29. }
  30. void pref(){
  31.  
  32. 	t[0]=0;
  33. 	for(int i=1;i<=n;i++){
  34. 		t[i] = t[i-1] + p[i];
  35. 	}
  36. }
  37. int main() {
  38. 	//freopen("CSBN.INP", "r", stdin);
  39. 	//freopen("CSBN.OUT", "w", stdout);
  40. 	ios::sync_with_stdio(false);
  41. 	cin.tie(nullptr);
  42. 	sang();
  43. 	pref();
  44. 	int q;
  45. 	cin >> q;
  46. 	while(q--){
  47. 		int l,r;
  48.  
  49. 		cin >> l >> r;
  50. 		cout << t[r] - t[l-1] << "\n";
  51.  
  52.  
  53. 	}
  54. }
Success #stdin #stdout 0.09s 52352KB
comments (?)
stdin
copy 
5
4 20
2 10
1 18
1 100
1 1000
stdout
copy 
6
4
7
25
168
https://ideone.com/Q4EdKF
language:
C++14 (clang 8.0)
created:
10 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!