prime-count-up-to.cpp

#include <memory>
#include <deque>
#include <cmath>
#include <cstring>
/*

    the algorithm used here is taken and modified from:
    https://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number/9704912#9704912

    There are many more room of possible imprevement.
    For example: caching the last called prime count inside a packed region, and some more.
    but I think this is enough for now

    PS. I might made any logical error. or maybe there is some miscalculation, I ddo't know...

    Best regard: Ery E. Wahyutama.

    9 March 2019;

    PPS. yes only one day and night working on this.
    
    Need C++14 or C++17 flag to compile; 
    compile with g++ prime-count-up-to.cpp -std=c++17
    
    input is hard coded change it to another if necessary. 

*/
// Count number of set bits in an int
std::uint32_t popCount(std::uint32_t n) {
    n -= (n >> 1) & 0x55555555;
    n = ((n >> 2) & 0x33333333) + (n & 0x33333333);
    n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
    return (n * 0x01010101) >> 24;
}

int* build_sieve(int n)
{
    int limit, root, count = 2;
    limit = (int)(n*(log(n) + log(log(n)))) + 3;
    root = (int)sqrt(limit);

    switch (limit % 6)
    {
    case 0:
        limit = 2 * (limit / 6) - 1;
        break;
    case 5:
        limit = 2 * (limit / 6) + 1;
        break;
    default:
        limit = 2 * (limit / 6);
    }

    switch (root % 6)
    {
    case 0:
        root = 2 * (root / 6) - 1;
        break;
    case 5:
        root = 2 * (root / 6) + 1;
        break;
    default:
        root = 2 * (root / 6);
    }

    int dim = (limit + 31) >> 5;
    int* sieve = new int[dim];
    std::memset(sieve, 0, dim * sizeof(int));

    for (int i = 0; i < root; ++i)
    {
        if ((sieve[i >> 5] & (1 << (i & 31))) == 0)
        {
            int start, s1, s2;
            if ((i & 1) == 1)
            {
                start = i * (3 * i + 8) + 4;
                s1 = 4 * i + 5;
                s2 = 2 * i + 3;
            }
            else
            {
                start = i * (3 * i + 10) + 7;
                s1 = 2 * i + 3;
                s2 = 4 * i + 7;
            }

            for (int j = start; j < limit; j += s2)
            {
                sieve[j >> 5] |= 1 << (j & 31);
                j += s1;

                if (j >= limit) break;

                sieve[j >> 5] |= 1 << (j & 31);
            }
        }
    }
    return sieve;
}

int nth(int nth, int* sieve)
{
    switch (nth)
    {
    case 1: return 2;
    case 2: return 3;
    }

    int count = 2;
    int i = 0;
    for (; count < nth; ++i)
    {
        auto mask = ~sieve[i];
        auto pop = popCount(mask);

        count += pop;
    }
    --i;
    int mask = ~sieve[i];

    int p = 31;
    for (; count >= nth; --p)
    {
        auto o = (mask >> p) & 1;
        count -= o;
    }
    return (3 * (p + (i << 5))) + 7 + (p & 1);
}

// this function really need optimization
// sorry I'm tired already...
bool is_prime(int val, int* sieve = nullptr)
{
    switch (val)
    {
    case 2:
    case 3:
    case 5:
    case 7:
        return true;
    }

    if ((val % 2) == 0) return false;
    if ((val % 3) == 0) return false;
    if ((val % 5) == 0) return false;
    if ((val % 7) == 0) return false;

    auto a = ((val - 7) / 3);
    auto b = a / 32;
    auto c = b * 32;
    // find p
    auto p = a - c;
    auto i = b;

    auto nearest = (3 * (p + (i << 5))) + 7 + (p & 1);

    if ((val - nearest) == 0)
    {
        if (!sieve)
            return true; // might be incorrect for prime factor

        // TODO: optimize this!
        int count_fix = 2;
        for (int a = 0; a <= i; ++a)
            count_fix += popCount(~sieve[a]);

        auto mask = ~sieve[i];
        int l = 31;
        for (; l >= 0; --l)
        {
            auto o = ((mask >> l) & 1);
            count_fix -= o;

            if (o == 1)
            {
                auto ll = l - 1;
                auto _temp = 3 * (ll + (i << 5)) + 7 + (ll & 1);
                if (_temp == val)
                    return true;
            }

        }
    }
    return false;
}

int main()
{
    std::deque<int> m_collection;

    int input = 1'000'000;
    int limit = sqrt(input);

    auto sieve = build_sieve(input);

    auto print = [&m_collection](int total)
    {
        auto last_index = m_collection.size() - 1;
        auto begin = m_collection.begin();
        for (auto itr = begin; itr != m_collection.end(); ++itr)
        {
            auto index = itr - begin;

            printf("%d", *itr);

            if (last_index == index)
            {
                printf(" = %d", total);
                return;
            }
            else
            {
                printf(" + ");
            }
        }
    };

    int total = 0;
    for (int i = 1; i <= limit; ++i)
    {
        int nth = ::nth(i, sieve);

        if (total + nth >= input)
        {
            // start substracting
            for (int j = i - 1; ; --j)
            {
                if (::is_prime(total, sieve))
                {
                    print(total);
                    delete[] sieve;
                    return 0;
                }
                nth = ::nth(j, sieve);
                total -= nth;
                m_collection.pop_back();
            }
        }

        total += nth;

        m_collection.push_back(nth);
    }
    print(total);
    delete[] sieve;
}

I notice that there is some logic error inside is_prime function;
here is what is wrong there..
I left the check for value equal to 5 and equal to 7, if it is then return true.
The shift to right 1 should be replaced with whether mod 2 is equal to zero (check for an even number) even better use
value & 1 == 0.. (purely logic error while writing the function)..

When the competition (well, quiz sort of). I will change the function and perform optimizing, cleaning, and tidying up.. so it will be production ready...

Best regards...