Monday, November 4, 2013

Recursive factorisation passing vector by reference

This program helped solve Project Euler problem 3.
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
//prototype a function that passes an int and a vector of ints by reference and which returns a result that uses push_back on a vector
void factorize(vector<unsigned long long>&, unsigned long long);

//target is the number you want to factorize
unsigned long long target = 0;
cout << "what number should I factorize?" << endl;
cin >> target;

//factor_list is the vector that is passed by reference
vector<unsigned long long> factor_list (1,1);

unsigned int start = clock();

//call factorize function - note although you are passing by reference this is only mentioned in the prototype and function, not the function call!!
factorize(factor_list, target);

cout << "time taken in milliseconds "  << clock()-start;

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

//size()method on vectors for number of elements
unsigned int j = 0;
while (j != factor_list.size()){
    cout << j << " one in the list " << factor_list[j] <<endl;
    j++;
}
    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
    }
}

No comments:

Post a Comment