Problem 12

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define NUM 501
#define DST 100

void
primeVector(vector<bool> *pv_table)
{
    pv_table->at(0) = pv_table->at(1) = false;

    for (vector<bool>::size_type i = 2, end = (vector<bool>::size_type)ceil(sqrt((double)(pv_table->size()))); i < end; i++)
    {
        if (pv_table->at(i))
        {
            for (vector<bool>::size_type j = i+i, endJ = pv_table->size(); j < endJ; j+=i)
            {
                pv_table->at(j)  = false;
            }
        }
    }
}

void
addPrime(vector<bool> *pv_table)
{
    vector<bool>::size_type st = pv_table->size();
    pv_table->resize(st+DST);
    for (vector<bool>::size_type i = 0; i < DST; i++)
    {
        pv_table->at(st+i) = true;
    }
    
    primeVector(pv_table);

    return;
}

int
main(int argc, char ** argv)
{
    vector<bool> v_table;
    vector<unsigned int>  v_prime;
    vector<bool>::size_type tail = 0;

    tail = v_table.size();
    addPrime(&v_table);
    for (vector<bool>::size_type i = tail, end = v_table.size(); i < end; i++)
    {
        if(v_table[i])
        {
            v_prime.push_back(i);
        }
    }

    int ans = -1;
    unsigned int tr = 6;
    int d = 4;
    while (1)
    {
        tr += d++;

        // 素因数分解
        vector<int> v_pf;
        int _tr = tr;
        int n = 1;
        for (vector<int>::size_type i = 0, end = v_prime.size(); i < end; i++)
        {
            int c = 1;
            while (1)
            {
                if (_tr%v_prime[i] == 0)
                {
                    v_pf.push_back(v_prime[i]);
                    _tr /= v_prime[i];
                    c++;
                }
                else
                {
                    break;
                }
            }
            if (c > 1)
            {
                n *= c;
            }
            if (_tr == 0)
            {
                break;
            }
        }        
                
        if (n >= NUM)
        {
            ans = tr;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}