#include <iostream>
#include <vector>
#include <cmath>

#define int64_t __int64

std::vector<int64_t> allPrimes;

int isPrime(int64_t param)
{
    if (param == 2)
        return 1;

    if ((param % 2) == 0)
        return 0;

    int64_t limit = (int64_t)sqrt((long double)param);

    // start at 2 since already done 2
    // even numbers cant be prime
    for (int i = 3; i <= limit; i += 2)
    {
        if ((param % i) == 0)
            return 0;
    }

    return 1;
}

int main()
{
    int64_t i;
    int64_t limit = 100000000 >> 1;

    // Precalculate all primes
    for (i = 2; i < limit; i++)
    {
        if (isPrime(i))
            allPrimes.push_back(i);

        if ((i % 1000000) == 0)
            std::cout << "Done a million" << std::endl;
    }

    std::cout << "Primes precalculated" << std::endl;

    int64_t goodOnes = 0;
    int64_t max = 100000000;
    int64_t numPrimes = allPrimes.size();
    int64_t j;

    // Check primes against each other (order doesnt matter)
    for (i = 0; i < numPrimes; i++)
    {
        for (j = i; j < numPrimes; j++)
        {
            // If the product is less than 10^8 we have found a number
            // with exactly 2 prime factors, else we move forward in the
            // prime vector
            if ((allPrimes[i] * allPrimes[j]) < max)
                goodOnes++;
            else
                break;
        }
    }

    std::cout << "Primes precalculated, good ones: " << goodOnes << std::endl;
    getchar();
}