#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <array>
#include <chrono>

using namespace std;

class muTimer
{
    using Clock = std::chrono::high_resolution_clock;
    bool active = false;
    Clock::duration   duration_;
    Clock::time_point start_ = Clock::now(), stop_ = Clock::now();

    muTimer(const muTimer&)             = delete;
    muTimer& operator=(const muTimer&)  = delete;
public:
    using ns       = std::chrono::nanoseconds;
    using mks      = std::chrono::microseconds;
    using ms       = std::chrono::milliseconds;
    muTimer() { reset(); start(); }
    ~muTimer() = default;
    muTimer& reset()
    {
        duration_ = std::chrono::nanoseconds(0);
        active    = false;
        return *this;
    }
    muTimer& start()
    {
        if (!active)
        {
            start_ = Clock::now();
            active = true;
        }
        return *this;
    }
    muTimer& stop()
    {
        if (active)
        {
            stop_      = Clock::now();
            duration_ += stop_ - start_;
            active     = false;
        }
        return *this;
    }
    template<typename T = mks>
        unsigned long long duration()
    {
        return static_cast<unsigned long long>
            (std::chrono::duration_cast<T>(stop_-start_).count());
    }
};


unsigned int odd_evenEn(unsigned int N)
{
    unsigned int count = 1;
    if (N%2) return false;
    unsigned int k = 0;
    while(N%2 == 0) { N/=2; ++k; }
    if (k%2 == 0) return 0;
    for(unsigned int p = 3; p*p <= N; p+=2)
    {
        if (N%p) continue;
        unsigned int k = 0;
        while(N%p == 0) { N /= p; ++k; }
        if (k%2) return 0;
        count *= 1+k;
    }
    if (N > 1) return 0;
    return count*k;
}

unsigned int odd_evenPr(unsigned int N)
{
    static array<unsigned int,6542> primes = []()
    {
        array<unsigned int,6542> p{2,3,5,7,11,13,17,19};
        for(unsigned int val = 23, count = 8; val < 65536; val += 2)
        {
            bool prime = true;
            for(unsigned int i = 0; i < count; ++i)
            {
                if (val % p[i] == 0) { prime = false; break; }
                if (p[i]*p[i] > val) break;
            }
            if (prime) p[count++] = val;
        }
        return p;
    }();


    unsigned int count = 1;
    if (N%2) return false;
    unsigned int k = 0;
    while(N%2 == 0) { N/=2; ++k; }
    if (k%2 == 0) return 0;
    for(unsigned int i = 1, p = primes[i]; p*p <= N; p=primes[++i])
    {
        if (N%p) continue;
        unsigned int k = 0;
        while(N%p == 0) { N /= p; ++k; }
        if (k%2) return 0;
        count *= 1+k;
    }
    if (N > 1) return 0;
    return count*k;
}


int main(int argc, char * argv[])
{
    {
        muTimer mt;
        for(unsigned int k = 1, cnt = 0; cnt < 5 && k < 1000000; ++k)
        {
            unsigned int N = 1850000000 + k;
            unsigned int q = odd_evenEn(N);
            if (q%2)
            {
                cout << k << "  " << q << endl;
                ++cnt;
            }
        }
        mt.stop();
        cout << "Total enum : " << mt.duration<muTimer::ms>() << " ms\n";
    }
    {
        muTimer mt;
        for(unsigned int k = 1, cnt = 0; cnt < 5 && k < 1000000; ++k)
        {
            unsigned int N = 1850000000 + k;
            unsigned int q = odd_evenPr(N);
            if (q%2)
            {
                cout << k << "  " << q << endl;
                ++cnt;
            }
        }
        mt.stop();
        cout << "Primes enum: " << mt.duration<muTimer::ms>() << " ms\n";
    }
}