fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. vector<int> seive (int n, int m)
  7. {
  8. 	vector<int> primes;
  9. 	vector<bool> state(m - n + 1, true);
  10.  
  11. 	for (int i = n; i <= m; i++)
  12. 	{
  13. 		for (int j = 2; j <= sqrt(m); j++)
  14. 		{
  15. 			int index = j*j - (n % j*j);
  16.  
  17. 			if (!state[index])	continue;
  18. 			if (i % (j * j) == 0)
  19. 			{
  20. 				state[index] = false;
  21. 				for (int k = index; k <= m; k += (j*j))
  22. 					state[k] = false;
  23. 			}
  24. 		}
  25. 	}
  26.  
  27. 	for (int i = 0; i < (m - n + 1); i++)
  28. 		if (state[i])	primes.push_back(i + n);
  29.  
  30. 	return primes;
  31. }
  32.  
  33. int main()
  34. {
  35. 	ios_base::sync_with_stdio(0);
  36. 	cin.tie(0);
  37. 	cout.tie(0);
  38.  
  39. 	int N, M;
  40. 	cin >> N >> M;
  41.  
  42. 	vector<int> a;
  43. 	a = seive(N, M);
  44.  
  45. 	for (int i = 0; i < a.size(); i++)
  46. 		cout << a[i] << ' ';
  47.  
  48. 	return 0;
  49. }
Success #stdin #stdout 0.01s 5400KB
comments (?)
stdin
copy 
1 10
stdout
copy 
1 2 4 5 6 8 9 10
https://ideone.com/ZwaPZq
language:
C++14 (gcc 8.3)
created:
1 year 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!