Наибольший общий делитель

Чтобы стать опытным программистом, важно понимать некоторые основные математические концепции. И это начинается с базового сложения, вычитания, умножения, вычисления по модулю, битов и многих других важных понятий, таких как простые числа, исключающее ИЛИ и НОД.

Что такое НОД?

Наибольший общий делитель (НОД) двух или более целых чисел, если хотя бы одно из них не равно нулю, представляет собой наибольшее положительное целое число, которое полностью делит оба числа, не оставляя остатка.

Например, НОД чисел 8 и 12 равен «4».

Интересно, почему? Позволь мне объяснить.

Исследование НОД

Давайте рассмотрим два целых числа: «a» и «b».

Пусть «x» — наибольшее целое число, которое может полностью разделить «a» и «b», не оставляя остатка.

А теперь подумайте, каким может быть диапазон «х»?

1 ‹= ‘x’ ‹= минимум(a, b)

Что теперь делать?

Если мы перечислим возможные значения «x» для «a» = 12 и «b» = 8.

x = {1, 2, 3, 4, 5, 6, 7, 8}, любое целое число больше 8 приводит к тому, что (b/x) становится равным 0.

Из набора значений «x» числа, которые полностью делят «a» и «b», равны [1, 2, 4], причем «4» является самым большим.

И вот мы наконец получаем: gcd(12, 8) = 4.

Эффективное вычисление НОД

Теперь, будучи программистом, вам нужно писать программы, которые работают быстро и эффективно. Итак, теперь наша цель — найти более быстрый способ вычисления НОД.

Но перед этим давайте установим некоторые свойства делимости, которые окажутся нам полезными в наших будущих начинаниях.

Теорема 1

Пусть «a» — целое число, а «b» — положительное целое число. Тогда существуют уникальные целые числа «q» и «r» такие, что 0 ‹= r‹ b и a=(b*q)+r.

Наверняка вы это знаете, или вы просто не распознали то, что здесь написано, на самом деле,

Дивиденд = делитель x частное + остаток

Итак, теперь вы поняли: мы говорим здесь об обычном разделении и его границах.

Это известно как правило делимости. Например, если a = 9 и b = 2, в результате деления получается частное 4 и остаток 1.

Следовательно, 9 = (4 * 2) + 1, а остаток удовлетворяет только что написанному условию: 0‹=r‹b.

Проще говоря, это означает, что остаток всегда будет меньше частного.

Теорема 2

Если а делится на х и b делится также на х, то (а + b) делится на х и (а — b) также делится на х.

Рассуждение заключается в представлении делимости как

а = q*x+0 и b = k*x+0.

Сложение этих уравнений дает a + b = x * (q + r), где u = a + b и v = q + r. Поскольку u = x * v + 0, u делится на x. Тот же принцип применим и к (а — б).

Информация о НОД

Пусть a и b — два целых числа, а g — их наибольший общий делитель. Таким образом, НОД(a, b) = g. Это означает, что g делит и a, и b, что приводит к выражениям:

  • а = р * г + 0 (уравнение I)
  • b = q * g + 0 (уравнение II)

Здесь p и q — частное, полученное при делении a и b на g.

Более того, если мы рассмотрим деление a на b, мы получим a = t * b + rem, где t — частное, а rem — остаток.

Подстановка значений из уравнений I и II дает g * (p — (t * q)) = rem.

Важно отметить, что это означает, что остаток rem делится на g. Это показывает, что g не только делит a и b, но также делит остаток, когда a делится на b. Следовательно, НОД(a, b) = НОД(b, остаток от деления а на b), что предлагает более эффективный подход к вычислению НОД.

Фактически, мы увидим, что это предоставит нам подход логарифмической временной сложности. Временная сложность — O(log n).

Реализация: перевод теории в код

Чтобы применить эти идеи на практике, давайте предоставим реализации как на C, так и на Java:

Реализация С++

#include <iostream>

// Function to compute the Greatest Common Divisor (GCD)
int gcd(int a, int b)
{
    // Base case: if b divides a completely, then b is the GCD
    if (a % b == 0)
        return b;
    // Recursive case: find GCD of b and remainder of a divided by b
    else
        return gcd(b, a % b);
}

int main()
{
    int a, b;
    
    // Input the two numbers
    std::cout << "Enter two numbers: ";
    std::cin >> a >> b;
    
    // Calculate the GCD using the gcd() function
    int x = gcd(a, b);
    
    // Output the GCD
    std::cout << "GCD of " << a << " and " << b << " is " << x << std::endl;
    
    return 0;
}

Java-реализация

import java.util.*;

public class GCDCalculator {

    // Function to compute the Greatest Common Divisor (GCD)
    static int gcd(int a, int b) {
        // Base case: if b divides a completely, then b is the GCD
        if (a % b == 0)
            return b;
        // Recursive case: find GCD of b and remainder of a divided by b
        else
            return gcd(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input the two numbers
        System.out.print("Enter two numbers: ");
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        // Calculate the GCD using the gcd() function
        int x = gcd(a, b);

        // Output the GCD
        System.out.println("GCD of " + a + " and " + b + " is " + x);

        scanner.close();
    }
}

Заключение

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

СДЕЛАЙТЕ ЭТО, ИЛИ МНЕ БУДУ ГРУСТНО 🥺

Было бы здорово, если бы вы рассказали мне что-то уникальное о gcd, которое вы знаете. Или какой-то вопрос, который вы задали на основе gcd и считаете, что им стоит поделиться с другими.

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

Кто я?

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

Кроме того, я пишу статьи для фрилансеров, поэтому вы можете связаться со мной по ссылке ниже.

Если вам понравилась эта статья, поддержите меня в этом начинании, подписавшись на меня на Medium и получайте последние обновления моих замечательных и полезных статей.

Вы можете побудить меня написать больше: https://ko-fi.com/medusaverse

Буду рад связаться с вами: https://linktr.ee/harshit_raj_14

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

https://medium.com/@Harshit_Raj_14/subscribe