fork(19) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXPR = (int)1e8;
  5. void calcPrimes() {
  6.     auto sum = 2LL;
  7.     int cnt = 1;
  8.  
  9.     const int S = round(sqrt(MAXPR));
  10.     vector<char> sieve(S + 1, true);
  11.     vector<array<int, 2>> cp;
  12.     for (int i = 3; i < S; i += 2) {
  13.         if (!sieve[i])
  14.             continue;
  15.         cp.push_back({i, (i * i - 1) / 2});
  16.         for (int j = i * i; j <= S; j += 2 * i)
  17.             sieve[j] = false;
  18.     }
  19.     vector<char> block(S);
  20.     int high = (MAXPR - 1) / 2;
  21.     for (int low = 0; low <= high; low += S) {
  22.         fill(block.begin(), block.end(), true);
  23.         for (auto &i : cp) {
  24.             int p = i[0], idx = i[1];
  25.             for (; idx < S; idx += p)
  26.                 block[idx] = false;
  27.             i[1] = idx - S;
  28.         }
  29.         if (low == 0)
  30.             block[0] = false;
  31.         for (int i = 0; i < S && low + i <= high; i++)
  32.             if (block[i])
  33.                 ++cnt, sum += (low + i) * 2 + 1;
  34.     };
  35.  
  36. 	cout << "sum = " << sum << endl;
  37. 	cout << "cnt = " << cnt << endl;
  38. }
  39.  
  40. int main() {
  41.     calcPrimes();
  42. 	return 0;
  43. }
Success #stdin #stdout 0.14s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sum = 279209790387276
cnt = 5761455
https://ideone.com/FFIlTC
language:
C++14 (clang 8.0)
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!