// Prim3r.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <windows.h>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <thread>
#include <atomic>
#include <algorithm>
#include <mutex>

//-----------------------------------------------------------------------------

typedef std::vector<UINT> uint_vect;

std::atomic_uint_fast32_t pool_at, pool_advance, pool_primes, pool_primes_need;
std::mutex pool_mutex, prime_mutex;
//-----------------------------------------------------------------------------

inline bool IsPrime(UINT num, uint_vect *vect)
{
    UINT primes_count;

    if(num <= 1)
    return false;

    {
        //std::lock_guard<std::mutex> l(prime_mutex);

        primes_count = vect->size();
    }

    for(UINT i = 0; i < primes_count; i++)
    {
        UINT p = vect->at(i);

        if(p * p > num)
        break;

        if((num % p) == 0)
        return false;
    }

    return true;
}

//-----------------------------------------------------------------------------

UINT FindPrimes(UINT from, UINT to, uint_vect *vect)
{
    UINT found = 0;

    for(UINT n = from; n < to; n++)
    {
        if(IsPrime(n, vect))
        {
            std::lock_guard<std::mutex> l(prime_mutex);

            vect->push_back(n);

            found += 1;
        }
    }

    return found;
}

//-----------------------------------------------------------------------------

void PrimeWorker(uint_vect *vect)
{
    while(pool_primes < pool_primes_need)
    {
        UINT start, end;

        {
            std::lock_guard<std::mutex> l(pool_mutex);

            start = pool_at;
            end   = start + pool_advance;

            pool_at = end;
        }

        UINT n = FindPrimes(start, end, vect);

        pool_primes += n;
    }
}

//-----------------------------------------------------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
    UINT find_them = 10000000;
    UINT amount    = 1000;

    uint_vect primes;

    primes.reserve(find_them / 4);

    LARGE_INTEGER perf_start, perf_end, perf_freq;

    printf("Looking for %u Primes...\n", find_them);

    pool_at = 0;
    pool_advance = amount;
    pool_primes  = 0;
    pool_primes_need = find_them;

    QueryPerformanceCounter(&perf_start);

    std::thread th1(PrimeWorker, &primes);
    std::thread th2(PrimeWorker, &primes);
    std::thread th3(PrimeWorker, &primes);
    std::thread th4(PrimeWorker, &primes);

    th1.join();
    th2.join();
    th3.join();
    th4.join();

    std::sort(primes.begin(), primes.end());

    QueryPerformanceCounter(&perf_end);

    QueryPerformanceFrequency(&perf_freq);

    float perf_time = (perf_end.QuadPart - perf_start.QuadPart) * 1000.0f / perf_freq.QuadPart;

    printf("Found %u primes in %.3fms (%u k/sec)\n", primes.size(), perf_time, (UINT)(primes.size() / perf_time));

    primes.resize(find_them);

    printf("First 10: ");

        for(int i = 0; i < 10; i++)
        {
            printf("%u ", primes[i]);
        }

    printf("\n");

    printf("Last 10: ");

        for(int i = primes.size() - 10; i < primes.size(); i++)
        {
            printf("%u ", primes[i]);
        }

    printf("\n");


    system("pause");

    return 0;
}