set intersection

I want to calculate the gcd of two numbers m and n by prime factorization and taking common factors like this. Take example m = 36 n = 48

vector<int> factors1 = prime_factorization(m); // 2 2 3 3 
vector<int> factors2 = prime_factorization(n); // 2 2 2 2 3
vector<int> intersection(10);
set_intersection(factors1.begin(), factors1.end(), factors2.begin(), factors2.end(), intersection.begin()); 

intersection is now 2 2 3 0开发者_Python百科 0 0 0 0 0 0. For this i must set the size of the vector beforehand. Also the remaining elements are set to 0. I don't want this to happen.

Is there a better way to do this? Using sets or anything else?

Also, how do i calculate the product of elements in the vector intersection (2*2*3) using stl ignoring the zeroes?

You can use a back-inserter:

vector<int> intersection;
set_intersection(..., back_inserter(intersection));

Note that there are much better ways of determining the GCD, such as Euclid's algorithm.

Oli's answer is best in the situation as you describe it. But if you were using a vector that already existed and had elements that you were writing over, and you wanted to chop off the extra numbers, you can do it a different way. By calling the vector member erase using the return value of set_intersection:

intersection.erase(
    set_intersection(factors1.begin(), factors1.end(), factors2.begin(), factors2.end(), intersection.begin()),
    intersection.end());