fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define all(a) a.begin() ,a.end()
  5.  
  6. vector<ll> sieve(ll n) 
  7. { 
  8. 	vector<bool> prime(n + 1, true); 
  9.  	prime[0] = false; 
  10. 	prime[1] = false; 
  11.  	for (ll i = 2; i*i <= n; i++) { 
  12.  
  13. 		// If prime[i] is not changed, then it 
  14. 		// is a prime 
  15. 		if (prime[i]) { 
  16.  
  17. 			// Update all multiples of p 
  18. 			for (ll j = i * i; j <= n; j += i) 
  19. 				prime[j] = false; 
  20. 		} 
  21. 	} 
  22.  
  23. 	// push all the primes into the vector ans 
  24. 	vector<ll> ans; 
  25. 	for (ll i = 0; i < n; i++) 
  26. 		if (prime[i]) 
  27. 			ans.push_back(i); 
  28. 	return ans; 
  29. } 
  30.  
  31. vector<ll> sieveRange(ll l , ll r){
  32. 	ll sqrt_r = sqrt(r);
  33. 	vector<ll>smallPrimes = sieve(sqrt_r);
  34. 	vector<bool>isPrime(r-l+1,true);
  35. 	for(ll p :smallPrimes){
  36. 		ll start = max(p*p , (l+p-1)/p*p);
  37. 		for(int j=start;j<=r;j+=p){
  38. 			isPrime[j-l]=false;
  39. 		}
  40. 	}
  41. 	vector<ll>ans;
  42. 	for(int i=0;i<isPrime.size();i++){
  43. 		if(isPrime[i] && (i+l)>1){
  44. 			ans.push_back(i+l);
  45. 		}
  46. 	}
  47. 	return ans;
  48. }
  49.  
  50. int main() {
  51. 	ll l =12;
  52. 	ll r = 50;
  53. 	vector<ll>ans = sieveRange(l,r);
  54. 	for(int x:ans)cout<<x<<" ";
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13 17 19 23 29 31 37 41 43 47 49
https://ideone.com/NXUL1A
language:
C++ (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!