设置交集

Question

我想通过素数因子分解和计算这样的常见因子来计算两个数m和n的gcd.例如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()); 

交集现在是2 2 3 0 0 0 0 0 0 0.为此,我必须事先设置向量的大小.其余元素也设置为0.我不希望发生这种情况.

有一个更好的方法吗？使用集合还是其他什么？

另外,如何使用stl忽略零来计算向量交集(2*2*3)中元素的乘积？

Answer 1

您可以使用后插件:

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

请注意,有更好的方法来确定GCD,例如Euclid的算法.

Answer 2

正如你所描述的那样,奥利的回答是最好的.但是如果你使用的是已经存在的矢量并且你正在编写的元素,并且你想要删除额外的数字,你可以采用不同的方式.通过erase使用set_intersection的返回值调用vector成员:

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