установить пересечение

Question

Я хочу вычислить gcd двух чисел m и n путем простой факторизации и использования общих факторов, подобных этому.Возьмем пример: 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. Я не хочу, чтобы это произошло.

Есть ли лучший способ сделать это?Используя множества или что-нибудь еще?

Кроме того, как рассчитать произведение элементов в векторном пересечении (2 * 2 * 3), используя stl, игнорируя нули?

Answer 1

Вы можете использовать задний вкладыш :

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

Обратите внимание, что существуют гораздо лучшие способы определения GCD, например алгоритм Евклида .

Answer 2

Ответ Оли лучший в ситуации, как вы ее описали.Но если вы использовали вектор, который уже существовал и имел элементы, которые вы переписывали, и вы хотели отрубить лишние числа, вы можете сделать это по-другому.Вызывая член вектора erase, используя возвращаемое значение set_intersection:

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