#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 } }
Monday, November 4, 2013
Recursive factorisation passing vector by reference
This program helped solve Project Euler problem 3.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment