constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }
inline unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}

constexpr unsigned long MAX_LIM = 1000000000; //pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;

unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное

auto set_primes = [](unsigned long idx) { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx) { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };

vector<unsigned long> Primes;

void makePrimes()
{
    for(unsigned long j = 9; j <= MAX_LIM; j += 3)
    {
        if (j%2) set_primes(j);
    }
    for(unsigned long i = 5; i <= SQR_LIM; i += 6)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += i)
        {
            if (j%2) set_primes(j);
        }
    }
    for(unsigned long i = 7; i <= SQR_LIM; i += 6)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += i)
        {
            if (j%2) set_primes(j);
        }
    }
    Primes.reserve(55000000);
    Primes.push_back(2);
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        Primes.push_back(i);
    }

}


vector<unsigned long> * factors(long long L, vector<unsigned long> * v = 0)
{
    if (v == 0) v = new vector<unsigned long>;
    if (L == 1) return v;
    for(auto f: Primes)
    {
        if (f*f > L) {
            v->push_back(L);
            return v;
        }
        if (L%f == 0)
        {
            v->push_back(f);
            return factors(L/f,v);
        }
    }
    return v;
}


int main(int argc, const char * argv[])
{
    makePrimes();
    printf("Total primes = %dn",Primes.size());

    for(long long i = 900000000000000000ll; i < 900000000000001000ll; ++i)
    {
        vector<unsigned long> * f = factors(i);
        for(auto x: *f)
        {
            printf("%lu ",x);
        }
        printf("%lldn",i);
        delete f;
    }

}

#include <iostream>
#include <chrono>

constexpr unsigned long N = 1000000000;
bool grid[N + 2];
unsigned long primes[51000000];
unsigned long primesCount;

inline void factors(unsigned long num)
{
    for (unsigned long i = 0; i < primesCount; ++i)
    {
        while (num % primes[i] == 0)
        {
            std::cout << primes[i] << ' ';
            num /= primes[i];
        }
    }
}

int main()
{
    auto start = std::chrono::high_resolution_clock::now();
    grid[0] = grid[1] = true;
    grid[2] = false;

    for (unsigned long p = 3, k; p*p <= N; p += 2)
    {
        if (! grid[p])
        {
            for (k = p*p; k <= N; k += p)
                grid[k] = true;
        }
    }
    primes[primesCount++] = 2;
    for (unsigned long p = 3, k; p <= N; p += 2)
    {
        if (! grid[p]) primes[primesCount++] = p;
    }
    for (unsigned long long num = 900000000000000000ll; num < 900000000000000100ll; ++num)
    {
        std::cout << num << " - ";
        factors(num);
        std::cout << 'n';
    }

    auto elapsedTime = std::chrono::duration_cast<
        std::chrono::milliseconds
    >(std::chrono::high_resolution_clock::now() - start);

    std::cout << elapsedTime.count() / 1000.0f << 'n'
              << "primes count: " << primesCount << 'n';
    return EXIT_SUCCESS;
}