fork download 
  1. #include <vector>
  2. #include <string>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <array>
  7. #include <chrono>
  8.  
  9. using namespace std;
  10.  
  11. class muTimer
  12. {
  13.     using Clock = std::chrono::high_resolution_clock;
  14.     bool active = false;
  15.     Clock::duration   duration_;
  16.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  17.  
  18.     muTimer(const muTimer&)             = delete;
  19.     muTimer& operator=(const muTimer&)  = delete;
  20. public:
  21.     using ns       = std::chrono::nanoseconds;
  22.     using mks      = std::chrono::microseconds;
  23.     using ms       = std::chrono::milliseconds;
  24.     muTimer() { reset(); start(); }
  25.     ~muTimer() = default;
  26.     muTimer& reset()
  27.     {
  28.         duration_ = std::chrono::nanoseconds(0);
  29.         active    = false;
  30.         return *this;
  31.     }
  32.     muTimer& start()
  33.     {
  34.         if (!active)
  35.         {
  36.             start_ = Clock::now();
  37.             active = true;
  38.         }
  39.         return *this;
  40.     }
  41.     muTimer& stop()
  42.     {
  43.         if (active)
  44.         {
  45.             stop_      = Clock::now();
  46.             duration_ += stop_ - start_;
  47.             active     = false;
  48.         }
  49.         return *this;
  50.     }
  51.     template<typename T = mks>
  52.         unsigned long long duration()
  53.     {
  54.         return static_cast<unsigned long long>
  55.             (std::chrono::duration_cast<T>(stop_-start_).count());
  56.     }
  57. };
  58.  
  59.  
  60. unsigned int odd_evenEn(unsigned int N)
  61. {
  62.     unsigned int count = 1;
  63.     if (N%2) return false;
  64.     unsigned int k = 0;
  65.     while(N%2 == 0) { N/=2; ++k; }
  66.     if (k%2 == 0) return 0;
  67.     for(unsigned int p = 3; p*p <= N; p+=2)
  68.     {
  69.         if (N%p) continue;
  70.         unsigned int k = 0;
  71.         while(N%p == 0) { N /= p; ++k; }
  72.         if (k%2) return 0;
  73.         count *= 1+k;
  74.     }
  75.     if (N > 1) return 0;
  76.     return count*k;
  77. }
  78.  
  79. unsigned int odd_evenPr(unsigned int N)
  80. {
  81.     static array<unsigned int,6542> primes = []()
  82.     {
  83.         array<unsigned int,6542> p{2,3,5,7,11,13,17,19};
  84.         for(unsigned int val = 23, count = 8; val < 65536; val += 2)
  85.         {
  86.             bool prime = true;
  87.             for(unsigned int i = 0; i < count; ++i)
  88.             {
  89.                 if (val % p[i] == 0) { prime = false; break; }
  90.                 if (p[i]*p[i] > val) break;
  91.             }
  92.             if (prime) p[count++] = val;
  93.         }
  94.         return p;
  95.     }();
  96.  
  97.  
  98.     unsigned int count = 1;
  99.     if (N%2) return false;
  100.     unsigned int k = 0;
  101.     while(N%2 == 0) { N/=2; ++k; }
  102.     if (k%2 == 0) return 0;
  103.     for(unsigned int i = 1, p = primes[i]; p*p <= N; p=primes[++i])
  104.     {
  105.         if (N%p) continue;
  106.         unsigned int k = 0;
  107.         while(N%p == 0) { N /= p; ++k; }
  108.         if (k%2) return 0;
  109.         count *= 1+k;
  110.     }
  111.     if (N > 1) return 0;
  112.     return count*k;
  113. }
  114.  
  115.  
  116. int main(int argc, char * argv[])
  117. {
  118.     {
  119.         muTimer mt;
  120.         for(unsigned int k = 1, cnt = 0; cnt < 5 && k < 1000000; ++k)
  121.         {
  122.             unsigned int N = 1850000000 + k;
  123.             unsigned int q = odd_evenEn(N);
  124.             if (q%2)
  125.             {
  126.                 cout << k << "  " << q << endl;
  127.                 ++cnt;
  128.             }
  129.         }
  130.         mt.stop();
  131.         cout << "Total enum : " << mt.duration<muTimer::ms>() << " ms\n";
  132.     }
  133.     {
  134.         muTimer mt;
  135.         for(unsigned int k = 1, cnt = 0; cnt < 5 && k < 1000000; ++k)
  136.         {
  137.             unsigned int N = 1850000000 + k;
  138.             unsigned int q = odd_evenPr(N);
  139.             if (q%2)
  140.             {
  141.                 cout << k << "  " << q << endl;
  142.                 ++cnt;
  143.             }
  144.         }
  145.         mt.stop();
  146.         cout << "Primes enum: " << mt.duration<muTimer::ms>() << " ms\n";
  147.     }
  148. }
  149.  
  150.  
Success #stdin #stdout 1.52s 5412KB
comments (?)
stdin 
Standard input is empty
stdout 
22792  81
144450  81
266112  27
387778  9
509448  27
Total enum : 1231 ms
22792  81
144450  81
266112  27
387778  9
509448  27
Primes enum: 292 ms
https://ideone.com/F2clOy
language:
C++14 (gcc 8.3)
created:
2 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!