fork download
copy 
  1. #include <set>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iostream>
  6. #include <iterator>
  7.  
  8. using namespace std;
  9.  
  10. void GetPrimesByQuadraticForms(vector<bool> &sieveAtkina)
  11. {
  12. 	int sqrtUpperBound = int(sqrt(sieveAtkina.size() - 1));
  13.  
  14. 	for (int x = 1; x <= sqrtUpperBound; x++)
  15. 	{
  16. 		for (int y = 1; y <= sqrtUpperBound; y++)
  17. 		{
  18. 			int result;
  19. 			result = ((4 * x * x) + (y * y));
  20. 			if (result <= sieveAtkina.size() - 1 && (result % 12 == 1 || result % 12 == 5))
  21. 			{
  22. 				sieveAtkina[result] = !sieveAtkina[result];
  23. 			}
  24. 			result = (3 * x * x) + (y * y);
  25. 			if (result <= sieveAtkina.size() - 1 && (result % 12 == 7))
  26. 			{
  27. 				sieveAtkina[result] = !sieveAtkina[result];
  28. 			}
  29. 			if (x > y)
  30. 			{
  31. 				result = ((3 * x * x) - (y * y));
  32. 				if (result <= sieveAtkina.size() - 1 && result % 12 == 11)
  33. 				{
  34. 					sieveAtkina[result] = !sieveAtkina[result];
  35. 				}
  36. 			}
  37. 		}
  38. 	}
  39. }
  40.  
  41. void DeleteSquaresNumbers(vector<bool> &sieveAtkina)
  42. {
  43. 	for (int j = 5; j < sqrt(sieveAtkina.size() - 1); j++)
  44. 	{
  45. 		if (sieveAtkina[j])
  46. 		{
  47. 			int n = j * j;
  48. 			for (int i = n; i <= sieveAtkina.size() - 1; i += n)
  49. 			{
  50. 				sieveAtkina[i] = false;
  51. 			}
  52. 		}
  53. 	}
  54. }
  55.  
  56. vector<bool> SearchPrimeNumbers(int upperBound)
  57. {
  58. 	vector<bool> sieveAtkina(upperBound + 1, false);
  59. 	for (int i = 2; i <= upperBound && i <= 3; i++)
  60. 	{
  61. 		sieveAtkina[i] = true;
  62. 	}
  63. 	GetPrimesByQuadraticForms(sieveAtkina);
  64. 	DeleteSquaresNumbers(sieveAtkina);
  65. 	return sieveAtkina;
  66. }
  67.  
  68. set<int> GeneratePrimeNumbersSet(int upperBound)
  69. {
  70. 	set<int> PrimeNumbers;
  71. 	vector<bool> sieve = SearchPrimeNumbers(upperBound);
  72. 	for (int i = 1; i <= upperBound; i++)
  73. 	{
  74. 		if(sieve[i])
  75. 		{
  76. 			PrimeNumbers.insert(i);
  77. 		}
  78. 	}
  79. 	return PrimeNumbers;
  80. }
  81.  
  82. int main()
  83. {
  84. 	auto x = GeneratePrimeNumbersSet(25);
  85. 	copy(x.begin(), x.end(), ostream_iterator<int>(cout, " "));
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3 5 7 11 13 17 19 23 25
https://ideone.com/nNOU7O
language:
C++ (gcc 8.3)
created:
4 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!