fork download
copy 
  1. #include <iostream>
  2. #include <bitset>
  3.  
  4. using namespace std;
  5.  
  6. typedef unsigned int uint;
  7.  
  8. const uint MaxValue = 4000000;
  9.  
  10. class Eratostenes {
  11. 	bitset<MaxValue/2> oddNotPrimes;
  12.  
  13. public:
  14. 	Eratostenes() {
  15. 		oddNotPrimes[0] = true;
  16. 		for (uint i=3; i<MaxValue; i+=2) {
  17. 			if (oddNotPrimes[i/2])
  18. 				continue;
  19. 			for (uint j=(i*3)/2; j<MaxValue/2; j+=i)
  20. 				oddNotPrimes[j] = true;
  21. 		}	
  22. 	}
  23.  
  24. 	bool isPrime(uint x) const {
  25. 		return x==2 || (x%2!=0) && !oddNotPrimes.test(x/2);
  26. 	}
  27.  
  28. 	uint nextPrime(uint x) const {
  29. 		uint y = (x+1)/2;
  30. 		do {
  31. 			y++;
  32. 		} while (oddNotPrimes.test(y));
  33. 		return 2*y+1;
  34. 	}
  35. };
  36.  
  37. int main() {
  38. 	Eratostenes primeTest;
  39. 	const uint begin = 3900001;
  40. 	for (uint i = 0; i<10; ++i) {
  41. 		cout << i << "\t" << primeTest.isPrime(i) << endl;
  42. 	}
  43.  
  44. 	for (uint i = begin; i<begin+100; i+=2)
  45. 		if (primeTest.isPrime(i))
  46. 			cout << i << endl;
  47.  
  48. 	cout << 30000 << "\t" << primeTest.nextPrime(30000) << endl;
  49. 	cout << 30100 << "\t" << primeTest.nextPrime(30100) << endl;
  50. 	cout << 3900067 << "\t" << primeTest.nextPrime(3900067) << endl;
  51.  
  52. 	return 0;
  53. }
  54.  
Success #stdin #stdout 0.02s 3572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0	0
1	0
2	1
3	1
4	0
5	1
6	0
7	1
8	0
9	0
3900067
3900097
30000	30011
30100	30103
3900067	3900097
https://ideone.com/ktPWqG
language:
C++14 (gcc 8.3)
created:
8 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!