fork download 
  1. #include <iostream>
  2. #include <cmath>
  3. #define MAX 1<<25
  4. using namespace std;
  5.  
  6. bool bits[MAX];
  7.  
  8. int count_primes(int until, int step) {
  9.     until++;
  10. 	int n = (until - 3) / 2;
  11. 	int limit = (int)sqrt(n);
  12.  
  13. 	for (int b = 0; b < n; b += step)
  14. 	{
  15. 		int end = min(n, b + step);
  16. 		for (int i = 0; i < limit; i++)
  17. 		{
  18. 			int k = i * 2 + 3;
  19. 			int kk = (k * k - 3) / 2;
  20.  
  21. 			int start = (b-i) / k * k + i;
  22. 			if (start < b) start += k;
  23. 			if (start < kk) start = kk;
  24.  
  25. 			if (!bits [i]) {
  26. 				for (int j = start; j < end; j += k)
  27. 					bits [j] = true;
  28. 			}
  29. 		}
  30. 	}
  31. 	int count = 1; //2 pre-counted
  32. 	for (int i = 0; i < n; i++)
  33. 		if (!bits[i]) count++; //the prime is i*2+3
  34. 	return count;	
  35. }
  36.  
  37. int main() {
  38.     clock_t begin_time = clock();
  39.  
  40.     cout << "Número de primos: " << count_primes(1<<25, 1<<16) << endl;
  41.     cout << "Segundos: " << double( clock () - begin_time ) /  CLOCKS_PER_SEC << endl;
  42. }
Success #stdin #stdout 0.08s 35864KB
comments (?)
stdin 
Standard input is empty
stdout 
Número de primos: 2063689
Segundos: 0.092588
https://ideone.com/haSEvj
language:
C++ (gcc 8.3)
created:
10 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!