Work out the number of divisors

This program works out the first triangular number to have more than five hundred divisors.

It does so by going through all of the triangular numbers, working out their prime factors which are stored in a vector and then passing the vector to another routine that adds up the total number of each different prime which is stored in another vector.

The total number of divisors is then found by adding one to the number of vectors and then multiplying up.

It is worth thinking about how to reduce the number of iterations and a theory to work out a starting point that would make sure that you were covering the number of factors. The program could also work on seeing if there is some limit or distribution of number of divisors, perhaps related to the frequency of primes themselves.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    void factorize(vector<unsigned long long>&, unsigned long long); //
    void factors_out(vector<unsigned long long>&);
    unsigned long int count_factors(vector<unsigned long long>&);

    //target is the number you want to factorize
    unsigned long long target = 0;
    unsigned long int total_factors = 0;
    unsigned int tri = 1;

        while (total_factors < 501){
            target = target + tri;
            tri++;
            vector<unsigned long long> factor_list (1,1);
            factorize(factor_list, target);
            total_factors = count_factors(factor_list);
        }

    cout << "the answer is " << target;
    return 0;
}


//factorize is called recursively and modifies the vector, vec, that is passed by reference
void factorize (vector<unsigned long long>& vec, unsigned long long num){

    unsigned long long test_num = 2; //start with 2 to see if 2 is a factor
    unsigned long long limit_num = num - 1; //change this to square root later in order to speed up
    bool found_factor = false; //assume you have not found a factor

    while (test_num < limit_num){
        if (num % test_num == 0){
            found_factor = true;
            vec.push_back(test_num); //vec was passed by reference
            num = num/test_num;
            test_num = limit_num; //you found a factor, so move to end of while loop to finish it
            }
        test_num++;
    }
    if (found_factor == true){
        factorize(vec, num); //if you found a factor, re run with the number rounded down
    }
    else {
        vec.push_back(num); //you didn't find a factor, so the last number must be prime as well!
        return; //you didn't find another factor so finish
    }
}


void factors_out (vector<unsigned long long>& output_vec){

cout << "size of factor list " << output_vec.size() << endl;

    //size()method on vectors for number of elements
    unsigned int j = 0;
    while (j != output_vec.size()){
        cout << j << " one in the list " << output_vec[j] << endl;
        j++;
    }
    cout << "end of list"  << endl;
}


/*
simplify count factors by not actually recording the different primes but
instead create a vector that counts up the number of each different type of prime
and then calculates the number of divisors at the end
*/

unsigned long int count_factors (vector<unsigned long long>& count_vec){

    vector<unsigned int> primes_count; // a vector to store the count of different primes
    unsigned long long current_prime = count_vec[0];  //the first prime - this will always be 1
    unsigned int count_current_prime = 1; //we have one example of the first prime

    //make a vector that totals up the primes
    for (unsigned int k = 1; k != count_vec.size(); k++){
        if (count_vec[k] == current_prime) {
            count_current_prime++;
        }
        else {
            primes_count.push_back(count_current_prime);
            count_current_prime = 1;
            current_prime = count_vec[k];
        }
    }

    //now work out the number of factors
    unsigned long int total_factors = 1;
    for (unsigned int h = 0; h != primes_count.size(); h++) {
        total_factors *= (primes_count[h] + 1);
     }

    return total_factors;
}