fork(3) download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <thread>
  5.  
  6. using namespace std;
  7.  
  8. #define REALMAXN 2000000000
  9. #define MAXN 2002000000
  10. #define SQRTN 45000
  11. #define BLOCKSIZE 500000
  12.  
  13.  
  14. // Automatically zeroed in G++
  15. // 0 means primes, 1 means composite number
  16. // Threated as block of bits
  17. unsigned long long big_sieve[MAXN/64];
  18.  
  19. // We are piglors and use global shared variables
  20. vector<pair<int, int>> big_primes;
  21.  
  22. void do_sieve(int start, int end, vector<pair<int, int>> primes) {
  23.     for (auto &p: primes) {
  24.         auto start_mul = start / p.first + 1;
  25.         if (start_mul % 2 == 0) {
  26.             start_mul += 1;
  27.         }
  28.         p.second = max(p.second, start_mul*p.first);
  29.     }
  30.     for (int i = start; i < end; i+=BLOCKSIZE) {
  31.         for (auto &p: primes) {
  32.             while (p.second < i + BLOCKSIZE) { 
  33.                 big_sieve[p.second/64] |= 1ll << (p.second % 64);
  34.                 p.second += p.first * 2;
  35.             }
  36.         }
  37.     }
  38. }
  39.  
  40. int main() {
  41.     vector<bool> sieve(SQRTN, true);
  42.     vector<pair<int, int>> small_primes;
  43.     for (int i = 2; i < SQRTN; i++) {
  44.         if (sieve[i]) {
  45.             for (int j = i*i; j < SQRTN; j += i) {
  46.                 sieve[j] = false;
  47.             }
  48.             if (i <= 13) {
  49.                 small_primes.push_back(make_pair(i, i*i));
  50.             } else {
  51.                 big_primes.push_back(make_pair(i, i*i));
  52.             }
  53.         }
  54.     }
  55.  
  56.     // Presieving with 2, 3, 5, 7, 11, 13
  57.     int lim = 2 * 3 * 5 * 7 * 11 * 13 * 32;
  58.     int limull = lim / 64;
  59.  
  60.     for (int i = 0; i < lim; i+=2) {
  61.         big_sieve[i/64] |= 1ull << (i % 64);
  62.     }
  63.     for (int i = 0; i < lim; i+=3) {
  64.         big_sieve[i/64] |= 1ll << (i % 64);
  65.     }
  66.     for (int i = 0; i < lim; i+=5) {
  67.         big_sieve[i/64] |= 1ll << (i % 64);
  68.     }
  69.     for (int i = 0; i < lim; i+=7) {
  70.         big_sieve[i/64] |= 1ll << (i % 64);
  71.     }
  72.     for (int i = 0; i < lim; i+=11) {
  73.         big_sieve[i/64] |= 1ll << (i % 64);
  74.     }
  75.     for (int i = 0; i < lim; i+=13) {
  76.         big_sieve[i/64] |= 1ll << (i % 64);
  77.     }
  78.  
  79.     for (int i = limull; i + limull < MAXN/64; i+=limull) {
  80.         memcpy(big_sieve + i, big_sieve, limull * 8);
  81.     }
  82.  
  83.     thread t1(do_sieve,          0,  500000000, big_primes);
  84.     thread t2(do_sieve,  500000000, 1000000000, big_primes);
  85.     thread t3(do_sieve, 1000000000, 1500000000, big_primes);
  86.     thread t4(do_sieve, 1500000000, 2000000000, big_primes);
  87.     t1.join();
  88.     t2.join();
  89.     t3.join();
  90.     t4.join();
  91.  
  92.     int total = 0;
  93.     for (int i = 0; i < REALMAXN/64; i++) {
  94.         total += __builtin_popcountl(big_sieve[i]);
  95.     }
  96.     // Correction by 5 due to 2,3,5,7,11,13 (and 1)
  97.     printf("%d %d\n", 5 + REALMAXN - total, small_primes.size());
  98. }
Success #stdin #stdout 2.21s 267904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
98222287 6
https://ideone.com/sgqp8c
language:
C++14 (gcc 8.3)
created:
6 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!