fork(13) download 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx")
  3. #include <bits/stdc++.h>
  4. using pii = std::pair<int, int>;
  5. const int NMAX = (int)1e9;
  6. const int SNMAX = (int)sqrt(NMAX) + 1;
  7. std::bitset<NMAX + 1> bits;
  8. int main() {
  9. 	bits[0] = bits[1] = 1;
  10. 	std::vector<pii> smallPrimes;
  11. 	for (int i = 2; i <= SNMAX; ++i) {
  12. 		if (!bits[i]) {
  13. 			smallPrimes.push_back({i, i * i});
  14. 			for (int j = i * i; j <= SNMAX; j += i) {
  15. 				bits[j] = 1;
  16. 			}
  17. 		}
  18. 	}
  19. 	const int blockSize = 1 << 18;
  20. 	for (int from = 0; from <= NMAX; from += blockSize) {
  21. 		int to = std::min(from + blockSize - 1, NMAX);
  22. 		for (pii& p : smallPrimes) {
  23. 			for (; p.second <= to; p.second += p.first) bits[p.second] = 1;
  24. 		}
  25. 	}
  26. 	bits.flip();
  27. 	//iterate over primes
  28. 	int64_t sum(0);
  29. 	int cnt(0);
  30. 	for (int p = bits._Find_first(); p < bits.size(); p = bits._Find_next(p)) {
  31. 		sum += p;
  32. 		cnt++;
  33. 	}
  34.     assert(bits.count() == cnt);
  35. 	std::cout << "sum = " << sum << std::endl;
  36. 	std::cout << "cnt = " << cnt << std::endl;
  37. 	return 0;
  38. }
Success #stdin #stdout 3.35s 125572KB
comments (?)
stdin 
Standard input is empty
stdout 
sum = 24739512092254535
cnt = 50847534
https://ideone.com/pNiP1M
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!