fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <ctime>
  5.  
  6. typedef uint64_t u64;
  7.  
  8. const uint8_t ONE = 1;
  9. const u64 F30[] = {1,7,11,13,17,19,23,29};
  10.  
  11. void markNonPrimes(const u64 start, const u64 num, const u64 lcm, const u64 limit, std::vector<uint8_t> &primes)
  12. {
  13.    for (u64 k = start; (lcm*k) < limit; k++)
  14.    {
  15.       u64 K = lcm*k;
  16.       if ((primes[k] & (ONE << 0)) && (K+F30[0]) % num == 0)
  17.          primes[k] &= ~(ONE << 0);
  18.       if ((primes[k] & (ONE << 1)) && (K+F30[1]) % num == 0)
  19.          primes[k] &= ~(ONE << 1);
  20.       if ((primes[k] & (ONE << 2)) && (K+F30[2]) % num == 0)
  21.          primes[k] &= ~(ONE << 2);
  22.       if ((primes[k] & (ONE << 3)) && (K+F30[3]) % num == 0)
  23.          primes[k] &= ~(ONE << 3);
  24.       if ((primes[k] & (ONE << 4)) && (K+F30[4]) % num == 0)
  25.          primes[k] &= ~(ONE << 4);
  26.       if ((primes[k] & (ONE << 5)) && (K+F30[5]) % num == 0)
  27.          primes[k] &= ~(ONE << 5);
  28.       if ((primes[k] & (ONE << 6)) && (K+F30[6]) % num == 0)
  29.          primes[k] &= ~(ONE << 6);
  30.       if ((primes[k] & (ONE << 7)) && (K+F30[7]) % num == 0)
  31.          primes[k] &= ~(ONE << 7);
  32.    }
  33. }
  34.  
  35. void getPrimesUpto(u64 limit)
  36. {
  37.    const u64 lcm = 30;
  38.    std::vector<uint8_t> primes(limit*0.035 + 1,0xff);
  39.  
  40.    u64 k = 1;
  41.    u64 n = 0;
  42.    u64 count=3-1;
  43.  
  44.    markNonPrimes(k, F30[1], lcm, limit, primes);
  45.    markNonPrimes(k, F30[2], lcm, limit, primes);
  46.    markNonPrimes(k, F30[3], lcm, limit, primes);
  47.    markNonPrimes(k, F30[4], lcm, limit, primes);
  48.    markNonPrimes(k, F30[5], lcm, limit, primes);
  49.    markNonPrimes(k, F30[6], lcm, limit, primes);
  50.    markNonPrimes(k, F30[7], lcm, limit, primes);
  51.  
  52.    while(lcm*k*lcm*k<limit)
  53.    {
  54.       const u64 K = lcm*k;
  55.       if(primes[k] & (ONE<<0))
  56.          markNonPrimes(k+1, K+F30[0], lcm, limit, primes);
  57.  
  58.       if(primes[k] & (ONE<<1))
  59.          markNonPrimes(k+1, K+F30[1], lcm, limit, primes);
  60.  
  61.       if(primes[k] & (ONE<<2))
  62.          markNonPrimes(k+1, K+F30[2], lcm, limit, primes);
  63.  
  64.       if(primes[k] & (ONE<<3))
  65.          markNonPrimes(k+1, K+F30[3], lcm, limit, primes);
  66.  
  67.       if(primes[k] & (ONE<<4))
  68.          markNonPrimes(k+1, K+F30[4], lcm, limit, primes);
  69.  
  70.       if(primes[k] & (ONE<<5))
  71.          markNonPrimes(k+1, K+F30[5], lcm, limit, primes);
  72.  
  73.       if(primes[k] & (ONE<<6))
  74.          markNonPrimes(k+1, K+F30[6], lcm, limit, primes);
  75.  
  76.       if(primes[k] & (ONE<<7))
  77.          markNonPrimes(k+1, K+F30[7], lcm, limit, primes);  
  78.  
  79.       k++;
  80.    }
  81.  
  82.    for(u64 k=0; lcm*k < limit; k++ )
  83.    {
  84.       for(u64 i =0; i<8; i++)
  85.          if(primes[k] & ONE<< i && lcm*k+F30[i] < limit) {count++;/*std::cout << lcm*k+F30[i] << " ";*/}
  86.    }
  87.  
  88.    std::cout  << "\n======\n"<< count << "\n";
  89. }
  90.  
  91. int main()
  92. {
  93.    clock_t start = clock();
  94.    getPrimesUpto(1000000);
  95.    std::cout << "\nTime: "<< clock() - start << std::endl;
  96. }
Success #stdin #stdout 0.55s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
======
78498

Time: 549974
https://ideone.com/peTwHI
language:
C++14 (gcc 8.3)
created:
9 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!