fork download 
  1. #include <iostream>
  2. #include <chrono>
  3. #include <vector>
  4. #include <memory>
  5.  
  6. class Myon
  7. {
  8. public:    
  9.     Myon()=default;
  10.  
  11. private:
  12.     static constexpr int block = 2 * 3 * 5 * 7 * 11 * 13 * 17;
  13.  
  14.     long target;
  15.  
  16. public:
  17.     void calc()
  18.     {
  19.         //Stopwatch sw = new Stopwatch();
  20.         //
  21.  
  22.         //target = long.Parse(Console.ReadLine());
  23.         std::cin >> target;
  24.  
  25.         //sw.Start();
  26.         auto time_start = std::chrono::high_resolution_clock::now() ;
  27.  
  28.  
  29.         first = std::unique_ptr<bool[]>(new bool[block]);
  30.         all = std::unique_ptr<int[]>(new int[block]);
  31.         c = 0;
  32.  
  33.         firstcalc();
  34.  
  35.         for (long i = block; i < target; i += block)
  36.         {
  37.             calc(i);
  38.         }
  39.  
  40.  
  41.         //Console.Error.WriteLine("prime count: " + count);
  42.         std::cerr << "prime count: " << count << std::endl;
  43.  
  44.         //sw.Stop();
  45.         auto time_end = std::chrono::high_resolution_clock::now() ;
  46.         auto sw = std::chrono::duration_cast< std::chrono::milliseconds >(
  47. 		 time_end -time_start ).count() ;
  48.  
  49.  
  50.         //Console.Error.WriteLine(sw.ElapsedMilliseconds + "ms");
  51.         std::cerr << sw << "ms" << std::endl;
  52.     }
  53.  
  54. private:
  55.     std::unique_ptr<bool[]> first;
  56.     std::unique_ptr<int[]>  all;
  57.     int c;
  58.     long count = 0;
  59.  
  60.     std::vector<int> primes;
  61.     static constexpr std::initializer_list<int const> firstp = { 2, 3, 5, 7, 11, 13, 17 };
  62.  
  63.     void precalc()
  64.     {
  65.         first[0] = true;
  66.         for (auto a : firstp)
  67.         {
  68.             for (int b = a; b < block; b += a)
  69.             {
  70.                 first[a] = true;
  71.             }
  72.         }
  73.     }
  74.  
  75.     //List<int> li = new List<int>();
  76.     std::vector<int> li;
  77.  
  78.     void firstcalc()
  79.     {
  80.         //primes = new List<int>();
  81.         for (auto p : firstp)
  82.         {
  83.             if (p > target) break;
  84.             addprime(p);
  85.             if ((long)p * p <= target)
  86.             {
  87.                 primes.push_back(p);
  88.                 for (int j = p + p; j < block; j += p)
  89.                 {
  90.                     first[j] = true;
  91.                 }
  92.             }
  93.         }
  94.         c++;
  95.         li.push_back(1);
  96.         for (int i = 19; i < block; i++)
  97.         {
  98.             if (first[i]) continue;
  99.             li.push_back(i);
  100.             if (all[i] == c) continue;
  101.             if (i <= target) addprime(i);
  102.             else break;
  103.             if ((long)i * i <= target)
  104.             {
  105.                 primes.push_back(i);
  106.                 for (int j = i + i; j < block; j += i)
  107.                 {
  108.                     all[j] = c;
  109.                 }
  110.             }   
  111.         }
  112.     }
  113.  
  114.     void calc(long b)
  115.     {
  116.         c++;
  117.         long max = b + block;
  118.         for (auto p : primes)
  119.         {
  120.             if ((long)p * p > max) break;
  121.             int f = (int)(b % p);
  122.             if (f != 0) f = p - f;
  123.             if ((f & 1) == 0) f += p;
  124.             for (int j = f; j < block; j += p + p)
  125.             {
  126.                 all[j] = c;
  127.             }
  128.         }
  129.  
  130.         for (auto i : li)
  131.         {
  132.             if (all[i] == c) continue;
  133.             long num = b + i;
  134.             if (num <= target) addprime(num);
  135.             else break;
  136.         }
  137.     }
  138.  
  139.     void addprime(long a)
  140.     {
  141.         count++;
  142.     }
  143.  
  144. };
  145.  
  146. constexpr std::initializer_list<int const> Myon::firstp;
  147.  
  148. auto main() -> int
  149. {
  150.     Myon().calc();
  151.     return 0;
  152. }
Success #stdin #stdout #stderr 0.88s 3680KB
comments (?)
stdin 
100000000
stdout 
Standard output is empty
stderr 
prime count: 5761455
880ms
https://ideone.com/e5xgrV
language:
C++14 (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!