pe012.cpp

#include <iostream>
#include <vector>
#include <memory>

#include "pe.h"

/*
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

    1: 1
    3: 1, 3
    6: 1, 2, 3,  6
   10: 1, 2, 5, 10
   15: 1, 3, 5, 15
   21: 1, 3, 7, 21
   28: 1, 2, 4,  7, 14, 28
   We can see that 28 is the first triangle number to have over five divisors.

   What is the value of the first triangle number to have over five hundred divisors?
*/

int get_first_tri_faster(unsigned int divisors, int max) {
    std::shared_ptr<std::vector<unsigned int> > factors(new std::vector<unsigned int>(max, 2));
    int tri = 0;
    int tri_index = 0;
    bool flag = false;
    for (int i = 2; i < max && !flag; ++i) {
        if (i > tri) {
            ++tri_index;
            tri += tri_index;
        }
        if (i==tri) {
            //std::cout << "Tri " << i << " has " << factors->at(i) << " divisors" << std::endl;
            if (factors->at(i) >= divisors) {
                flag = true;
                //std::cout << "FOUND SOLUTION: " << tri << std::endl;
            }
        }
        if (!flag) {
            for (int o = i*2; o < max; o+=i) {
                ++factors->at(o);
            }
        }
    }
    return tri;
}

//disgustingly slow
namespace slow {
    bool has_x_divisors(int number, int divisors) {
        int div_count = 0;
        for (int i = number; i>0; --i) {
            if (number % i == 0) {
                ++div_count;
            }
        }
        return div_count >= divisors;
    }

    unsigned long factorial(unsigned long f) {
        return f==0? 1 : f * factorial(f-1);
    }

    int get_first_tri(int min_divisors) {
        unsigned long min_val = factorial(min_divisors);

        //generate triangle numbers
        bool flag = false;
        unsigned long tri = 0;
        for (int i = 1; !flag; ++i) {
            tri+=i;
            std::cout << "Testing tri: " << tri << std::endl;
            if (tri >= min_val && has_x_divisors(tri, min_divisors)) {
                flag = true;
            }
        }
        return tri;
    }
}

class pe012 : public pe_base {
    void run_test() {
        int ans = 76576500;
        int value = get_first_tri_faster(500, 77000000);
        check("012", ans, value);
    }
};

int main(int argc, char** argv) {
    pe012 test;
    test.go();
    std::cout << test.get_message() << std::endl; 
    return test.exit_code();
}