fork download
copy 
  1. //print prime numbers from range..l....to....r
  2. #include<bits/stdc++.h>
  3. using namespace std; 
  4. #define all(v) v.begin(), v.end() 
  5. typedef long long ll;
  6. vector<ll> sieve(ll n) 
  7. { 
  8. 	vector<bool> prime(n + 1, true); 
  9.  	prime[0] = false; 
  10. 	prime[1] = false; 
  11. 	long long int m = sqrt(n); 
  12.  	for (ll p = 2; p <= m; p++) { 
  13.  
  14. 		// If prime[p] is not changed, then it 
  15. 		// is a prime 
  16. 		if (prime[p]) { 
  17.  
  18. 			// Update all multiples of p 
  19. 			for (ll i = p * p; i <= n; i += p) 
  20. 				prime[i] = false; 
  21. 		} 
  22. 	} 
  23.  
  24. 	// push all the primes into the vector ans 
  25. 	vector<ll> ans; 
  26. 	for (ll i = 0; i < n; i++) 
  27. 		if (prime[i]) 
  28. 			ans.push_back(i); 
  29. 	return ans; 
  30. } 
  31.  
  32. vector<ll> sieveRange(ll start, ll end) 
  33. { 
  34. 	// find primes from [0..end] range 
  35. 	vector<ll> ans = sieve(end); 
  36.  
  37. 	// Find index of first prime greater than or 
  38. 	// equal to start 
  39. 	// O(sqrt(n)loglog(n)) 
  40. 	ll lower_bound_index = lower_bound(all(ans), start) - ans.begin(); 
  41. 	ans.erase(ans.begin(), ans.begin() + lower_bound_index); 
  42.  
  43. 	return ans; 
  44. } 
  45.  
  46.  
  47. int main() {
  48.     ll l,r;
  49.     l = 2 ; 
  50.     r = 103;
  51.     r++;
  52.     ll start = l; 
  53.     ll end = r; 
  54.     vector<ll> ans = sieveRange(start, end); 
  55.     for (auto i : ans) {
  56.         cout<<i<<endl ; 
  57.     }
  58. 	return 0; 
  59. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
https://ideone.com/rreDN5
language:
C++14 (gcc 8.3)
created:
8 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!