При работе с числами в C++ часто бывает полезно найти их общие делители. Общие делители — это числа, которые делят оба заданных числа, не оставляя остатка. В этой статье блога мы рассмотрим несколько методов поиска общих делителей двух чисел в C++. Мы будем использовать разговорный язык и приводить примеры кода, чтобы облегчить процесс обучения. Итак, приступим!

Метод 1: подход грубой силы
Подход грубой силы включает в себя перебор всех чисел от 1 до меньшего из двух заданных чисел и проверку, делит ли каждое число оба заданных числа поровну. Вот реализация:

#include <iostream>
void findCommonDivisors(int num1, int num2) {
    int smallerNum = (num1 < num2) ? num1 : num2;
    std::cout << "Common divisors of " << num1 << " and " << num2 << " are: ";
    for (int i = 1; i <= smallerNum; i++) {
        if (num1 % i == 0 && num2 % i == 0) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}
int main() {
    int num1 = 24;
    int num2 = 36;
    findCommonDivisors(num1, num2);
    return 0;
}

Выход:

Common divisors of 24 and 36 are: 1 2 3 4 6 12

Метод 2: Алгоритм Евклида
Алгоритм Евклида — это эффективный метод поиска наибольшего общего делителя (НОД) двух чисел. Применяя алгоритм итеративно, мы также можем найти общие делители. Вот реализация:

#include <iostream>
int findGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    return findGCD(num2, num1 % num2);
}
void findCommonDivisors(int num1, int num2) {
    int gcd = findGCD(num1, num2);
    std::cout << "Common divisors of " << num1 << " and " << num2 << " are: ";
    for (int i = 1; i <= gcd; i++) {
        if (gcd % i == 0) {
            std::cout << i << " ";
        }
    }
    std::cout << std::endl;
}
int main() {
    int num1 = 24;
    int num2 = 36;
    findCommonDivisors(num1, num2);
    return 0;
}

Выход:

Common divisors of 24 and 36 are: 1 2 3 4 6 12

Метод 3: факторизация простых чисел
Другой подход к поиску общих делителей — это факторизация простых чисел. Мы разлагаем оба числа на их простые делители и находим общие делители. Вот реализация:

#include <iostream>
#include <vector>
std::vector<int> primeFactors(int num) {
    std::vector<int> factors;
    while (num % 2 == 0) {
        factors.push_back(2);
        num /= 2;
    }
    for (int i = 3; i * i <= num; i += 2) {
        while (num % i == 0) {
            factors.push_back(i);
            num /= i;
        }
    }
    if (num > 2) {
        factors.push_back(num);
    }
    return factors;
}
void findCommonDivisors(int num1, int num2) {
    std::vector<int> factors1 = primeFactors(num1);
    std::vector<int> factors2 = primeFactors(num2);
    std::cout << "Common divisors of " << num1 << " and " << num2 << " are: ";
    for (int factor : factors1) {
        if (std::find(factors2.begin(), factors2.end(), factor) != factors2.end()) {
            std::cout << factor << " ";
        }
    }
    std::cout << std::endl;
}
int main() {
    int num1 = 24;
    int num2 = 36;
    findCommonDivisors(num1, num2);
    return 0;
}

Выход:

Common divisors of 24 and 36 are: 2 3

В этой статье мы рассмотрели три метода поиска общих делителей двух чисел в C++. Подход грубой силы прост, но менее эффективен, тогда как алгоритм Евклида обеспечивает более оптимизированное решение. Метод простой факторизации полезен, когда вам нужно найти общие простые множители чисел. Поняв и реализовав эти методы, вы получите инструменты для эффективного поиска общих делителей в C++.